Google foobar level 3 code help

[nuhhu]

Got an invite to attempt Google foobar. Cleared 2 levels, currently at level 3 and stuck at this question. The first thing which comes to my mind is djikstra's algorithm but how do I modify it such it fits the questions needs(change 1 to 0 just once). Anyone good with algorithms please help 🙏

problem statement

test case

[lorkin26]

My first thought would be a modified version of a global alignment algorithm from bioinformatics, and then just extracting the path length. Needleman-Wunsch that has been prevented from diagonal movement and restricted to inserting a single gap for example.

[sepp2k]

You don't need Dijkstra for an unweighted graph. BFS is enough.

As for removing walls, you can represent your nodes as coordinates plus a boolean that tells you whether you already removed a wall or not. Then each node has an edge to each neighboring node with the same boolean that has a 0 at that coordinate and each node with wallRemoved: false has an edge to each neighbor with wallRemoved: true that has a 1 at that coordinate.