탈출 룸

면접 대비

시간 제한2초메모리 제한512 MB

요약

정수로 채워진 M×N 격자에서 (1,1)에서 시작해 값 x인 칸에서 a×b=x인 칸 (a,b)로 이동할 때, 격자 안에서 (M,N)에 도달할 수 있는지 판정한다.

난이도: 보통10점 중 5점
유형: 그래프, BFS, 정수론, 수학
정답자: 아직 제출이 없습니다

문제

어떤 방에서 탈출할 수 있는지 판별해야 한다. 방은 M행 N열 격자이고, 각 칸에는 양의 정수가 하나씩 들어 있다. 행은 1, 2, ..., M, 열은 1, 2, ..., N으로 번호를 매긴다. r행 c열 칸을 (r, c)로 나타낸다.

(1, 1)에서 시작해 (M, N)으로 나간다. 값 x가 들어 있는 칸에 있을 때, a × b = x를 만족하는 임의의 칸 (a, b)로 점프할 수 있다. 예를 들어 6이 들어 있는 칸에 있으면 (2, 3)으로 점프할 수 있다.

6이 들어 있는 칸에서 점프할 수 있는 칸은 (2, 3), (3, 2), (1, 6), (6, 1) 네 개까지 있다. 방이 5행 6열 격자라면 6행이 없으므로 앞의 세 번의 점프만 가능하다.

입력

입력의 첫째 줄에 정수 M이 주어진다. (1 ≤ M ≤ 1000) 둘째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 1000) 나머지 입력은 M행 N열 방의 각 칸에 들어 있는 양의 정수를 준다. M개의 줄로 이루어지고, 각 줄에는 1 000 000 이하의 양의 정수 N개가 공백 하나로 구분되어 주어진다.

출력

방에서 탈출할 수 있으면 yes, 그렇지 않으면 no를 출력한다.

예제1

예제 1
입력
```
3
4
3 10 8 14
1 11 12 12
6 2 3 9
```
예상 출력
```
yes
```