[2019 SCPC 2차 예선]

폭격

적의 공장들을 파괴하기 위해 폭격을 계획하고 있다.

적국은 열의 격자칸으로 생각한다.

각 칸에는 공장이 있거나 없을 수 있다. 폭탄 하나는 3행 3열에 있는 공장을 모두 파괴할 수 있다.



아래 그림에서 적국은 6행 11열의 격자칸이며 4개의 공장이 있다. 2개의 폭탄으로 모든 공장을 파괴한 모습을 볼 수 있다.

적국의 공장 배치를 입력으로 받아 가능한 최소 개수의 폭탄으로 공장을 모두 파괴하는 방법을 출력하는 프로그램을 작성하라.

 





이 문제는 주최측이 계산한 답에 대한 비례로 점수가 주어진다. 아래 채점 방식을 확인하라.


입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수  가 주어지고,

이후 차례로  개의 테스트 케이스가 주어진다. 

각 테스트 케이스의 첫 줄에는 격자칸의 행수 과 격자칸의 열 수 이 주어진다. 다음 개의 줄에 길이 인 0/1로 이루어진 문자열이 주어진다. 글자 하나가 격자칸에 공장이 있는지의 여부를 나타낸다. 0이면 공장이 없고, 1이면 공장이 있다는 뜻이다.

 

출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.

다음 폭탄의 개수  를 출력한다. 그 다음 개의 줄에 각 폭탄의 위치를, 파괴되는 범위의 제일 왼쪽 위 격자칸의 행번호 , 열번호 의 쌍으로 출력한다.

( 즉, 제일 왼쪽 위 격자칸의 행번호는 1이고 열번호는 1이다.) 폭탄의 위치를 출력하는 순서는 상관이 없다.

입출력예

입력
1
6 11
00000000000
00000000000
00000100000
00100010000
00000000000
00001000000
출력
Case #1
2
4 3
3 5

돌아가기