Red Knight's Shortest Path

  • + 0 comments

    Really liked the problem, basically used everything there are with bfs.

    Python solution:

    def is_valid(i, j, n):
        if i >= 0 and i < n and j >= 0 and j < n:
            return True
            
        return False
        
        
    def get_neighbours(loc, n):
        i, j = loc[0], loc[1]
        name = ['UL', 'UR', 'R', 'LR', 'LL', 'L']
        dr = [-2, -2, 0, 2, 2, 0]
        cr = [-1, 1, 2, 1, -1, -2]
        res = []
        
        for d in range(6):
            if is_valid(i+dr[d], j+cr[d], n):
                res.append([(i+dr[d], j+cr[d]), name[d]])
        
        return res
        
    def printShortestPath(n, i_start, j_start, i_end, j_end):
        # Print the distance along with the sequence of moves.
        parent_dict = {(i_start, j_start): None}
        front_tier = [(i_start, j_start)]
        _next = []
        lvl = 0
        tgt = (i_end, j_end)
        
        def print_res(v):
            res = []
            cur = v
            while True:
                parent = parent_dict[cur]
                
                if parent is None:
                    for i in range(len(res)-1, -1, -1):
                        print(res[i], end=' ')
                    return
                
                res.append(parent[1])
                cur = parent[0]
                
        while front_tier:
            for v in front_tier:
                if v == tgt:
                    print(lvl)
                    print_res(v)
                    return
                    
                neighbours = get_neighbours(v, n)
                for neighbour in neighbours:
                    if neighbour[0] not in parent_dict:
                        _next.append(neighbour[0])
                        parent_dict[neighbour[0]] = [v, neighbour[1]]
            
            lvl += 1
            front_tier = _next
            _next = []
        
        print('Impossible')