Shortest Path with Rectangular Obstacles

Problem Statement

Shortest Path with Rectangular Obstacles A rectangular board is made of N * M square cells. The bottom-left cell is (0, 0) and the top-right cell is (N - 1, M - 1) . The first coordinate x runs over 0 .. N - 1 and the second coordinate y runs over 0 .. M - 1 . R rectangular obstacles are placed on the board. Obstacle K is given by its bottom-left corner (X1[K], Y1[K]) and its top-right corner (X2[K], Y2[K]) , and it blocks every cell (x, y) with X1[K] <= x <= X2[K] and Y1[K] <= y <= Y2[K] . Both corners are part of the obstacle — the coordinates name cells, not the lines between them. Obstacles may overlap each other freely; a cell covered by two obstacles is simply blocked, exactly as if it were covered by one. You start on cell (0, 0) and want to reach cell (N - 1, M - 1) . In one move you step from your current cell to a cell sharing a side with it — up, down, left or right — provided the destination is inside the board and is not blocked. Diagonal moves are not allowed.