You are tasked with finding the shortest path from the top left of the grid to the bottom right where you only ever incur costs of 1 and 0. This smells like a 0-1 BFS.

An alternative (and IMO, more intuitive solution) to 0-1 BFS: if two adjacent squares have the same colours, we can move freely between them without any extra cost. The problem is simply the unit-weight shortest path problem in a graph where the nodes are blocks of vertices with equal costs.

With these constraints you can code Dijkstra's or if you know it, you can code 0-1BFS

It's an 0-1 BFS problem. You can learn it from here

This is 0-1 BFS problem and it can be solve in O(nm).

Different to normal BFS,when we walk through a free way,we put the node in the front of the queue(if the shortest distance changed).When we walk through a cost way,put the node in the back of the queue(if the shortest distance changed).It can be proved that a node will not be push in the queue for over 2 times.

So the complexity is O(nm).

Thanks to all of you !this community is"the best ever" :)