Minimal cost path in wall-breaking maze

Question

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:

1. Only movement to one of four adjacent cells is allowed.
2. 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.
3. 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
++++++++
.......+
.......+
++++++++
+.......
+.......
++++++++

Answer 1

JavaScript (ES7),  198 185 179  178 bytes

Expects a matrix of integers with -1 for a wall and 0 for an empty cell. Returns a matrix of Boolean values.

m=>(g=(Y,w,n,X)=>w>=W&&w>W|n>N?0:m[Y+1]||1/m[Y][X+1]?m.map((r,y)=>r.map((v,x)=>v>0?1:(X-x)**2+(Y-y)**2^1?0:r[r[x]=1,g(y,w-v,-~n,x),x]=v)):o=g(-1,W=w,N=n))(0,0,W=++m[0][0]/0,0)&&o

Try it online!

Commented

This is a depth-first search. Visited cells are marked with 1. We keep track of the number of broken walls in w and the total number of visited cells in n. We abort as soon as the current path is worse than the best path found so far.

m => (                         // m[] = input matrix
  g = (                        // g is a recursive function taking:
    Y, w, n, X                 //   (X, Y) = current position
                               //   w = number of broken walls
  ) =>                         //   n = number of visited cells
  w >= W && w > W | n > N ?    // if (w, n) is worse than (W, N):
    0                          //   abort
  :                            // else:
    m[Y + 1] ||                //   if there's a cell below the current cell
    1 / m[Y][X + 1] ?          //   or a cell on the right:
      m.map((r, y) =>          //     for each row r[] at position y in m[]:
        r.map((v, x) =>        //       for each value v at position x in r[]:
          v > 0 ?              //         if v is positive:
            1                  //           yield 1
          :                    //         else:
            (X - x) ** 2 +     //           if the squared distance between
            (Y - y) ** 2 ^ 1 ? //           (X, Y) and (x, y) is not equal to 1:
              0                //             do nothing
            :                  //           else:
              r[r[x] = 1,      //             mark r[x] as visited by setting it to 1
                g(y, w - v,    //             do a recursive call at (x, y) with n+1
                  -~n, x),     //             if v = -1, w is also incremented
                x              //             actual index ...
              ] = v            //             ... to restore r[x] to v afterwards
        )                      //       end of inner map()
      )                        //     end of outer map()
    :                          //   else (bottom-right cell):
      o = g(-1, W = w, N = n)  //     update (W, N) and use a last recursive call
                               //     with X undefined and Y=-1 to build the output o
)(0, 0, W = ++m[0][0] / 0, 0)  // initial call to g at (0, 0); set the cell at (0, 0)
                               // to 1 and set W to +inf
&& o                           // return o

The purpose of the last recursive call o = g(-1, W = w, N = n) is to create a copy of the current maze where all visited cells are marked with true and all other cells are marked with false.

For this call, it's important to notice that:

• because W = w and N = n, the abort test is always false
• because Y = -1, the test on m[Y + 1] is always true
• because X is undefined, the squared distance is always NaN

Therefore, what is actually done is simply:

m.map((r, y) => r.map((v, x) => v > 0 ? 1 : 0))

Answer 2

Charcoal, 92 bytes

≔⟦⟧θＷＳ⊞θι⊞υ⟦⁰¦⁰ω⟧≔⟦⟧ηＦυ«⪫θ¶←Ｆ§ι²✳κ+¿∨ⅈⅉＦruld«≔⊟ＫＤ²✳κζＦ№#.∨ζ+⊞υＥι⁺μ⎇⁼ν²κ⁼ν⌕#.ζ»⊞ηι⎚»Ｆ⊟⌊η✳ι+¦+

Try it online! Link is to verbose version of code. Times out for larger grids (can just about do 3×8 but can't do 4×6). Takes grid in example format and outputs using +s and spaces. Explanation:

≔⟦⟧θＷＳ⊞θι

Input the grid.

⊞υ⟦⁰¦⁰ω⟧

Start with an initial state of no .s, no #s and no moves. (Strictly speaking this is incorrect but all paths must include the initial square so it cancels out.)

≔⟦⟧η

Start with no paths that reach from the end to the start.

Ｆυ«

Perform a breadth-first search of the states.

⪫θ¶←

Draw the input to the canvas, leaving the cursor at the end point.

Ｆ§ι²✳κ+

Draw the path so far.

¿∨ⅈⅉ

If the start hasn't been reached, then:

Ｆruld«

Loop over the orthogonal directions.

≔⊟ＫＤ²✳κζ

Look at the next character in that direction.

Ｆ№#.∨ζ+

If the character is a # or a ., then...

⊞υＥι⁺μ⎇⁼ν²κ⁼ν⌕#.ζ

Create a new state, formed by adding to the existing state; for index 2, add the current direction; for index 1, add 1 if the character is a .; for index 0, add 1 if the character is a #. Push this state to the list of states.

»⊞ηι

But if the start was reached, then record this state.

⎚»

Clear the canvas ready for the next state (or the final output).

Ｆ⊟⌊η✳ι+¦+

Get the minimum state, which is that with the fewest walls, or for states with equal walls, the one with the fewest non-walls (which is equivalent to the shortest path). (For states with equal wall and path length, the tie is broken by preferring paths that go left rather than up from the end.) Draw this state, plus the final position.

Much faster 101-byte version readily handles all the test cases:

≔⟦⟧θＷＳ⊞θι⊞υ⟦⁰¦⁰ω⟧≔⟦⟧ηＷ∧υ⊟υＦ∨¬η‹ιη«⪫θ¶←Ｆ§ι²✳λ+¿∨ⅈⅉＦruld«≔⊟ＫＤ²✳λζＦ№#.∨ζ+⊞υＥι⁺ν⎇⁼ξ²λ⁼ξ⌕#.ζ»≔ιη⎚»Ｆ⊟η✳ι+¦+

Try it online! Link is to verbose version of code. Explanation:

≔⟦⟧θＷＳ⊞θι

Input the grid.

⊞υ⟦⁰¦⁰ω⟧

Create the initial state.

≔⟦⟧η

Start with no path.

Ｗ∧υ⊟υ

Perform a depth-first search of the states, by removing the most recently added state each time.

Ｆ∨¬η‹ιη«

If we don't have a path yet, or it's longer than our path so far, then:

⪫θ¶←Ｆ§ι²✳λ+

Draw the input and the path so far.

¿∨ⅈⅉＦruld«≔⊟ＫＤ²✳λζＦ№#.∨ζ+⊞υＥι⁺ν⎇⁼ξ²λ⁼ξ⌕#.ζ»

If the start hasn't yet been reached then consider all possible steps and push the resulting state to the list of states.

≔ιη

Otherwise this must be the shortest path so far, so save it.

⎚»

Clear the canvas ready for the next state (or the final output).

Ｆ⊟η✳ι+¦+

Draw the shortest path found.

Answer 3

Python3, 378 bytes

def f(b):
 Q,W=len(b),len(b[0])
 q,d=[(0,0,[(0,0)],0)],{}
 for x,y,p,c in q:
  if(x,y)==(Q-1,W-1):d[c]=p;continue
  for X,Y in[(1,0),(0,1),(-1,0),(0,-1)]:
   if 0<=x+X<Q and 0<=y+Y<W and(T:=(x+X,y+Y))not in p and(((F:='#'!=b[x+X][y+Y])and(c not in d or len(p)+1<=len(d[c])))or(not d or(c+1<=max(d)and(c+1 not in d or len(p)+1<=len(d[c+1]))))):q+=[(*T,p+[T],c+(not F))]
 return d

Try it online!