등차 직사각형

면접 대비

시간 제한1초메모리 제한128 MB

요약

격자에서 빈 칸을 유리수로 채워 모든 행과 열이 등차수열이 되도록 만들 수 있는지 판별하는 문제입니다.

난이도: 보통10점 중 6점
유형: 수학, 행렬, 구현
정답자: 아직 제출이 없습니다

문제

등차수열 수업이 끝난 뒤, 선생님은 철수에게 숙제를 냈다. R × C 격자의 일부 칸에는 정수가 적혀 있고, 나머지 칸은 비어 있다. 철수가 할 일은 빈 칸을 알맞은 수로 채워 등차 직사각형(arithmetic rectangle) 을 만드는 것이다. 등차 직사각형이란 각 행과 각 열의 수들이, 나타나는 순서대로 등차수열을 이루는 직사각형을 말한다.

예를 들어 다음은 3 × 5 등차 직사각형이다.

 1 3 5 7 9
 2 2 2 2 2
 3 1 -1 -3 -5

일부 칸이 점(.)으로 대체된 정수 격자가 주어진다. 점들을 적절한 유리수로 바꾸어 등차 직사각형을 만들 수 있는지 판별하라.

참고: 등차수열이란 이웃한 두 항의 차가 항상 일정한 수열을 말한다.

입력

첫째 줄에 격자의 크기를 나타내는 두 양의 정수 R과 C가 주어진다. 이어서 R개의 줄이 주어지며, 각 줄에는 공백 하나로 구분된 C개의 토큰이 있다. 각 토큰은 점(.)이거나 정수이다.

출력

모든 점을 유리수로 바꾸어 격자 전체를 등차 직사각형으로 만들 수 있으면 Yes를, 만들 수 없으면 No를 한 줄에 출력하라.

제한

1 ≤ R, C ≤ 50
격자에 주어지는 각 정수는 -100 이상 100 이하이다.

예제4

예제 1
입력
```
3 5
. . 3 . 5
. . . 5 .
. . . . 7
```
예상 출력
```
Yes
```
예제 2
입력
```
1 6
4 . . 0 . .
```
예상 출력
```
Yes
```
예제 3
입력
```
1 4
1 2 . 2
```
예상 출력
```
No
```
예제 4
입력
```
3 3
1 . .
. 2 .
. . 3
```
예상 출력
```
Yes
```