Micro and Maze

3.7

3 votes
Graph, Algorithms, Flood fill, Easy, Ready, Approved
Problem

Micro just bought a maze, that can be represented as a matrix A of size N×M, where rows are numbered from 1 to N and columns are numbered from 1 to M. Each cell of the matrix can be either 0 or 1. If a cell is 0, that means it cannot be visited and if it is 1, then it can be visited. Allowed moves are up, down, left and right. Help Micro to find out if he can reach from the cell (1,1) to the cell (N,M), it is guaranteed that the cells (1,1) and (N,M) have value 1.

Input:
First line consists of a two space separated integers denoting N and M.
Following N lines consists of M space separated integers denoting the matrix A.

Output:
Print "Yes" (without quotes), if Micro can reach from cell (1,1) to (N,M) otherwise print "No" (without quotes).

Constraints:
1N,M10
0A[i][j]1

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The path is (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)

Editor Image

?