Hello I'm stuck in this problem: you are given a maze of size n*m (n,m<=1000),every cell has a number written on it and you need to go from cell (0,0) to cell(n-1,m-1) with minimum cost. you can move up,down,left,right .if you want to go to cell (x,y) and the number in this cell is different from number of current one then cost is increased otherwise cost is unchanged. link any help ! and Thanks
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" :)