import java.util.Scanner;
// 침투 - DFS - s2
public class ex13565 {
static int n,m;
static int board[][];
static int[] dx={0,1,0,-1};
static int[] dy={1,0,-1,0};
static boolean flag;
public static void DFS(int x,int y){
if(x==n-1){
flag=true;
return;
}
board[x][y]=2;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx>=0 && nx<n && ny>=0 && ny<m && board[nx][ny]==0){
DFS(nx,ny);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
board = new int[n][m];
for (int i=0; i<n; i++) {
String temp = sc.next();
for (int j=0; j<m; j++) {
board[i][j]=temp.charAt(j)-'0';
}
}
for(int i=0; i<m; i++){
if(flag==true) break;
if(board[0][i]==0){
DFS(0,i);
}
}
if(flag==true) System.out.println("YES");
else System.out.println("NO");
}
}
위에서 아래로 전류를 흘려보내야한다. 0으로 입력된곳이 전류가 흐를 수 있다. 1행을 훑으면서 DFS()를 호출해주고 4방향으로 다음좌표로 DFS()를 재귀호출한다. 지나온길은 다시 돌아가지 않기 위해서 임의로 2로 바꿔준다. 이런식으로 진행하다가 재귀가 마지막행에 도착했을 때 flag를 참으로 상태를 변경해주고 바로 return시킨다. 그렇게 DFS()를 끝내고 결과를 출력한다.!! 기본적인 DFS문제이다.