Rat in a Maze
Mediumjavapythonccppjavascript
Given a square grid where 1 is an open cell and 0 is a blocked cell, determine whether there is a path from the top-left cell (0,0) to the bottom-right cell (N-1,N-1), moving only up, down, left or right through open cells, without visiting any cell twice.
Input Format
The first line contains an integer N. Each of the next N lines contains N space-separated integers (0 or 1).
Output Format
Print 1 if such a path exists, otherwise print 0.
Example 1
Input
3 1 0 0 1 1 0 0 1 1
Output
1
Explanation: A route through open cells reaches the bottom-right corner.
- 1 <= N <= 12
- Each cell is 0 or 1