Optimising rook movement using DP

Question

A rook is a piece in the strategy board game of chess which can move horizontally or vertically through any number of unoccupied squares. More formally in one step, the rook can move in any one of the following directions {UP, DOWN, LEFT, RIGHT}, any number of squares till the squares are unoccupied.

Given the initial location (A, B) of the rook, the final destination (C, D) and the orientation of the chess board, we have to find the minimum number of steps required by the player to move the rook to the desired destination or tell that it is impossible provided all the other pieces on the chess board are stationary.

Unlike the normal chess board, for this problem the chess board is of the dimensions N x M. The orientation of the board is represented as 0/1 2D string array where 0 denotes empty square and 1 denotes occupied square.

My first attempt at this problem is using a standard BFS approach.

from collections import deque
class Solution:

    def solve(self, A, B, C, D, board):
        # @param A, B: (x, y) co-ordinates of start position
        # @param C, D: (x, y) co-ordinates of target position
        # @param board : list of strings
        # @return minimum moves required or impossible

        seen = set()

        def neighbors(i, j):
            @param i, j: co-ordinates of current position
            @return list with all possible valid moves

            nei = []
            x, y = i - 1, j
            while x >= 0 and board[x][y] != '1':
                nei.append((x, y))
                x -= 1

            x, y = i + 1, j
            while x < len(board) and board[x][y] != '1':
                nei.append((x, y))
                x += 1

            x, y = i, j - 1
            while y >= 0 and board[x][y] != '1':
                nei.append((x, y))
                y -= 1

            x, y = i, j + 1
            while y < len(board[0]) and board[x][y] != '1':
                nei.append((x, y))
                y += 1

            return nei

        def bfs(i, j):
            que = deque([(i, j, 0)])

            while que:
                m, n, level = que.popleft()
                seen.add((m, n))

                if m == C and n == D:
                    return level

                for x, y in neighbors(m, n):
                    if (x, y) not in seen:
                        que.append((x, y, level + 1))
                        seen.add((x, y))

            return -1

        return bfs(A, B)

However this approach is not efficient enough as the board can be very large(~1000x1000).

There is a lot of recomputation going on in the bfs approach. How would I write the DP approach with memoization?

Answer 1

Dynamic programming for shortest path problems tends to just look like a shortest path problem on a related graph. Indeed, one way to solve this in O(nm) time would be to make a graph where each node represents not just a position on the board but also which direction the rook is moving in, if any. Each node in the graph has a cost-zero arc to the node representing the next square in the same direction, as well as cost-one arcs to the nodes that represent the same position but with other directions. The number of nodes blows up by a factor of 4 (plus one for the start node) but the number of neighbors drops from O(n + m) to at most 4, which is much sparser than your current graph.

You need to implement something like Dijkstra's algorithm, but instead of a heap you can use a doubly-linked list. If you're traversing an arc of cost zero, put the head on the front of the list. If it's cost one, put it on the back.

Here's some neighbor-finding code (untested, use at your own risk).

# The start node is (x, y, None).
# Returns a list of pairs (neighbor, edge cost).
def neighbors(node, board):
    x, y, direction = node
    if direction is not None:
        dx, dy = direction
        if 0 <= x + dx < len(board) and 0 <= y + dy < len(board[x + dx]) and board[x + dx][y + dy] != '1':
            yield (x + dx, y + dy, direction), 0
    for newdirection in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
        if newdirection != direction:
            yield (x, y, newdirection), 1

Dijkstra in Python would normally look something like

import heapq

def dijkstra(source, board):
    heap = [(0, source)]
    distance = {}
    while heap:
        cost, node = heapq.heappop(heap)
        if node in distance:
            continue
        distance[node] = cost
        for neighbor, edgecost in neighbors(node, board):
            heapq.heappush(heap, (cost + edgecost, neighbor))
    return distance

If edgecost is always zero-one, then you can do

import collections

def specialdijkstra(source, board):
    heap = collections.deque([(0, source)])
    distance = {}
    while heap:
        cost, node = heap.popleft()
        if node in distance:
            continue
        distance[node] = cost
        for neighbor, edgecost in neighbors(node, board):
            (heap.append if edgecost else heap.appendleft)((cost + edgecost, neighbor))
    return distance