Inspired by this Puzzling challenge.
Challenge
Given a 2D rectangular grid where each cell is either an empty space or a wall, find the path (or one of the paths) from the top left cell to the bottom right, which satisfies the following:
- Only movement to one of four adjacent cells is allowed.
- The path breaks (or passes through) the minimal number of walls possible. In other words, a longer path that breaks fewer walls is preferred over a shorter path that breaks more walls.
- Among all paths that satisfy
2., the path is the shortest in terms of the number of cells visited in total.
The input can be taken as a matrix (or any equivalent) containing two distinct values to represent empty spaces and walls. The top left and bottom right cells are guaranteed to be empty.
Output the path as a grid (of the same dimensions as the input) containing two distinct values, one for the cells that are part of the path and the other for the rest.
Standard code-golf rules apply. Shortest code in bytes wins.
Test cases
In the following examples, the input uses .# for empty/wall, and the output uses .+ for non-path/path.
Input
..#..#..
Output
++++++++
Input
.#...
...#.
Output
+.+++
+++.+
Input
....
....
....
....
Output
++++
...+
...+
...+ (or any other path of same length)
Input
..#..
..#..
..#..
Output
+++++
....+
....+ (or any other path of same length that breaks only one walls)
Input
.#.#.
##.##
.###.
Output
+++++
....+
....+ (or 3 other possible answers)
Input
.......
######.
.......
.######
....#..
Output
+++++++
......+
......+
......+
......+
Input
.....#..
#######.
#######.
........
.#######
.#######
....#...
Output
++++++++
.......+
.......+
++++++++
+.......
+.......
++++++++