격자에서 도달 가능성


답안 제출

Points: 8
시간 제한: 2.0s
메모리 제한: 1G

문제 유형

직사각형 격자의 각 칸은 이동할 수 있는 칸 또는 벽이다. 이동할 수 있는 칸에서는 상하좌우로 인접한 이동할 수 있는 칸으로 움직일 수 있다.

시작 칸에서 도착 칸까지 이동할 수 있는지 알아보자.

입력

첫째 줄에 격자의 세로 크기 \(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

코멘트

현재 작성된 코멘트가 없습니다.