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

Help needed in Infinite Grid Atcoder problem
Автор code_warrior, история, 4 года назад, По-английски

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

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

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

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.

→ Ответить