code_warrior's blog

By code_warrior, history, 5 months ago, In English

Can anyone share his approach or idea of solving this beautiful problem. I couldn't get any way to solve this.The tutorial given , is in japanese. I used the google translate and whatever little i got to know is that we only need to check if it is possible to reach the bottom rightmost cell of a grid of size(h*((2h-1)*w)) form (1,1).If it is, then the answer is yes,else no. Please, reply if someone can help!

Infinite Grid

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If it isn't possible to do it in one box, it won't be possible no matter how many you join. If it is possible in one box, all you need to check is if it is possible in two boxes. If it is still doable in two then answer will be yes no matter how many you join. To check the case for two boxes you only need to check the first and last column of the first box after performing dfs. If any of the visited cells in the first column is at the same level as any of the visited cells in the last column, you will be able to transition into the next box using that cell and finally to the end.