Algorithm to find a shortest past under a special condition

Question

I am trying to come up with an algorithm that calculates the length of shortest rectangle movement in a given bitmap.

For example, let's say we have a 24x24 bitmap where 1 is black pixel and 0 is a white pixel.

{{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,1,1,1,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,1},
 {0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0},
 {1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0},
 {0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
 {0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
 {0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0},
 {0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,1,0,0,0,1,1,1,1,0,0,1,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0},
 {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1},
 {0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0},
 {0,0,1,0,0,1,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,0},
 {0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,0,0,0,0}}

This game is played on an n x n map of black/white pixels and the player moves a rectangle through this map. In the player's rectangle movement, it should not contain a black pixel. In a single rectangle movement, the player can replace the current rectangle r with any rectangle r2 that either contains r or is contained in r.

Initially, the player starts at the upper-left corner and tries to reach the bottom right pixel.

Under this condition, I am trying to find an algorithm to get the shortest rectangular move needed to reach the bottom right corner.

The input of the algorithm that I am using will be the map[n,n] which just looks like the bitmap above.

What is a good approach, or a good way to think about this problem?

Answer 1

Use a pathfinding algorithm, such as BFS, A*, or some other suitable algorithm. Here each rectangle is treated as a vertex of the graph, and you imagine an edge from rectangle r1 to rectangle r2 if that's an allowed move (if you currently have rectangle r1, you can get to r2 in a single step).

Think of the rectangle as the "state" of the system at any point in time. When you want to explore the statespace of a system, pathfinding algorithms are often worth a try.