|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||264||136||96||50.000%|
Professor Kim is in the process of developing a new fabric material such that the electrical current percolates. The cross section of the new fabric can be shown in the two-dimensional M × N grid. We assume that the top of the grid is the outer side of the fabric and the bottom is the inner side. The black colored cell insulates the current while the white cell conducts the current. The current travels from the outer side to the inner side of the fabric only through the white cells that are adjacent to each other. When the white cells are connected diagonally, the current cannot flow (see Figure 1). The professor wants to test whether the current could percolate from the outer side to the inner side through the material or not.
For example, the following Figure 1(a) shows that the current percolates through the material but Figure 1(b) does not:
|(a) The current percolates.||(b) The current does not percolate.|
Figure 1. Two examples.
When the information on each cell is given, write a program that computes whether the current can pass through the material or not.
Your program is to read from standard input. The first line of the input contains two integers M (2 ≤ M ≤ 1,000) and N (2 ≤ N ≤ 1,000) which represent the size of the fabric. In the following M lines, the information about each cell is given. Each line consists of N characters which composed by ‘0’ or ‘1’. The character ‘0’ represents the conduct cell and ‘1’ represents the insulate cell.
Your program is to write to standard output. If the current can pass through the material from the top to the bottom, print YES. If not, print NO.
5 6 010101 010000 011101 100011 001011
8 8 11000111 01100000 00011001 11001000 10001001 10111100 01010000 00001011