Escaping the Moving Maze
InterviewTime limit2sMemory limit512 MB
An 8x8 board with walls that shift down one row each second; decide if a character moving first each second can reach the top-right cell.
- Level
Medium5 of 10
- Topics
- BFS, Simulation, Graph, Implementation
- Solved
- No attempts yet
Problem
Wookje made a game for his school homework where you escape from an 8×8 chessboard. Every cell of the chessboard is either empty or a wall. Wookje's character starts in the bottom-left cell and must move to the top-right cell.
The special feature of this game is that the walls move. Every second, all walls move down one row, and a wall in the bottom row disappears because there is no row below it. Each second, Wookje's character can move to an adjacent cell (horizontally, vertically, or diagonally) or stay in place. The character can only move into empty cells.
During each second, Wookje's character moves first, and then the walls move. If a wall moves into the cell where the character is, the character can no longer move.
Determine whether Wookje's character can reach the top-right cell.
Input
The state of the chessboard is given over 8 lines. '.' is an empty cell, and '#' is a wall. The bottom-left cell is never a wall.
Output
Output 1 if Wookje's character can reach the top-right cell, or 0 otherwise.