딸기와 토마토

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

요약

길이 K인 딸기 선분 하나와 토마토 선분 하나의 합집합이 주어질 때, 두 선분이 겹치는 모든 칸을 찾는다.

난이도: 보통10점 중 7점
유형: 구현, 완전 탐색, 배열, 누적 합
정답자: 아직 제출이 없습니다

문제

즈티와 레오가 사는 집 앞마당에는 $N\times M$ 크기의 작은 텃밭이 있다. 텃밭의 좌측 상단의 좌표는 $(1, 1)$ 이며, 우측 하단의 좌표는 $(N, M)$ 이다. 텅 빈 텃밭이 허전해 보인 둘은 각자 원하는 작물을 텃밭에 심고 예쁘게 키워보기로 했다. 즈티는 $K$ 칸 이상인 가로 또는 세로 줄 하나를 고른 후 그 줄에서 임의의 연속한 $K$ 개의 칸에 모두 딸기 씨앗을 심었고, 레오는 같은 방법으로 토마토 씨앗을 심었다. 텃밭을 벗어나서 씨앗을 심을 수는 없다. 텃밭의 각 칸에 종류와 상관없이 씨앗이 존재하는지가 주어질 때, 딸기와 토마토가 같이 자랄 칸의 좌표를 전부 구해보자. 단, 씨앗에서 작물이 자라지 않는 경우는 없으며, 조건에 맞는 입력만 주어진다.

입력

첫 번째 줄에 $N, M, K$ 가 공백으로 구분되어 주어진다. $(1 \le N,M \le 2\\,000, 1 \le K \le \max(N,M))$

두 번째 줄부터 $N$ 개의 줄에 각 칸의 씨앗 존재 여부를 나타내는 $M$ 개의 정수가 공백으로 구분되어 주어진다. $1$ 은 씨앗이 존재한다는 것, $0$ 은 존재하지 않는다는 것을 의미한다.

출력

첫 번째 줄에 딸기와 토마토가 같이 자랄 칸의 수를 출력한다.

딸기와 토마토가 같이 자랄 칸이 한 개 이상이라면, 두 번째 줄부터 한 줄에 하나씩 딸기와 토마토가 같이 자랄 칸의 좌표를 첫 번째 좌표가 증가하는 순으로, 첫 번째 좌표가 같으면 두 번째 좌표가 증가하는 순으로 출력한다.

예제2

예제 1
입력
```
3 4 3
0 1 0 0
0 1 1 1
0 1 0 0
```
예상 출력
```
1
2 2
```
예제 2
입력
```
3 4 4
1 1 1 1
1 1 1 1
0 0 0 0
```
예상 출력
```
0
```