Блог пользователя Eddagdeg

Автор Eddagdeg, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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