Rat In A Maze

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types

magicalsoup has a pet rat. He puts him in a square maze, with walls and pathways. He always puts him at the top left corner, and the exit is at the bottom right corner. The rat can move in the 4 directions left, right, up and down. The maze is composed of N \times N numbers, of either 0 or 1. 0 indicates the rat can move there, while a 1 indicates there is a wall and the rat cannot move there or pass through there. At the end of the maze, is a piece of cheese. The rat really loves cheese, help him get to the cheese!

Constraints

1 \le N \le 500

Input Specification

The first line contains an integer, N, the size of the maze.

An N \times N size grid, with 0 and 1s.

Output Specification

Print out either yes or no, if the rat can reach the end of the maze or not.

Sample Input

4
0 0 1 1
0 0 0 1
0 0 1 0
0 1 0 0

Sample Output

no

Comments


  • 0
    rnpmat08_v2  commented on Jan. 5, 2024, 12:01 a.m.

    For anyone wondering, the starting square will not contain a 1


  • 18
    p1geon  commented on Dec. 1, 2019, 7:09 p.m.

    Shouldn't this be labelled as graph theory?