격자에서 도달 가능성
직사각형 격자의 각 칸은 이동할 수 있는 칸 또는 벽이다. 이동할 수 있는 칸에서는 상하좌우로 인접한 이동할 수 있는 칸으로 움직일 수 있다.
시작 칸에서 도착 칸까지 이동할 수 있는지 알아보자.
입력
첫째 줄에 격자의 세로 크기 \(H\)와 가로 크기 \(W\)가 공백으로 구분되어 주어진다.
다음 \(H\)개의 줄에 길이가 \(W\)인 문자열이 주어진다. 1은 이동할 수 있는 칸, 0은 벽을 뜻한다.
마지막 줄에 시작 칸의 행과 열 \(S_r,S_c\), 도착 칸의 행과 열 \(E_r,E_c\)가 공백으로 구분되어 주어진다. 행은 위에서부터, 열은 왼쪽부터 \(1\)번으로 센다.
출력
시작 칸에서 도착 칸까지 이동할 수 있으면 YES, 그렇지 않으면 NO를 출력한다.
제한
- \(1 \le H,W\)
- \(H \times W \le 1,000\)
- 시작 칸과 도착 칸은 모두 이동할 수 있는 칸이다.
- 시작 칸과 도착 칸은 같을 수 있다.
예제 입력 1
4 5
11100
00100
01111
01001
1 1 4 5
예제 출력 1
YES
예제 입력 2
3 4
1100
0000
0011
1 1 3 4
예제 출력 2
NO
코멘트