Eddagdeg's blog

good problem from Dev skill
By Eddagdeg, history, 6 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply