1회 중앙대학교 컴퓨터공학과 프로그래밍 경진 대회 C번 문제 : 색깔 바꾸기
다음처럼 3*3 정사각형 모양이 있다. 각 칸은 검은색이나 흰색이다.
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
칸을 하나 누르면 그 칸과 이웃한 칸들의 색이 반대로 변한다. 예를 들어, 1번을 누르면 1,2,4,5 번의 색이 반대로 변한다. 6번을 누르면 2,3,5,6,8,9 번의 색이 반대로 변한다. 물론 5번을 누르면 1,2,3,4,5,6,7,8,9 번의 색이 반대로 변한다. 예를 들어 아래 그림 (a)에서 6번칸을 누르면 그림 (b)로 변하고, 여기서 1번칸을 누르면 그림 (c)가 되어 모두 하얗게 변한다. (a) 그림을 모두 하얗게 만드는데 누르는 회수는 2이다.
(b는 검은색 w는 하얀색)
그림 (a)
그림 (b)
그림 (c)
각 칸이 검은 색이나 흰색으로 칠해진 3*3 정사각형이 주어질 때, 이를 모두 흰색이 되도록 하는데, 누르는 회수를 최소로 하는 방법을 찾는 프로그램을 작성하시오.
b | w | b |
b | w | b |
w | b | b |
그림 (b)
b | b | w |
b | b | w |
w | w | w |
그림 (c)
w | w | w |
w | w | w |
w | w | w |
각 칸이 검은 색이나 흰색으로 칠해진 3*3 정사각형이 주어질 때, 이를 모두 흰색이 되도록 하는데, 누르는 회수를 최소로 하는 방법을 찾는 프로그램을 작성하시오.
입력
입력은 표준 입력이다. 입력의 첫줄에 테스트 케이스의 개수를 나타내는 정수 T (10 이하) 가 주어진다. 다음 T줄의 각 줄마다 테스트 케이스가 주어진다. 테스트 케이스는 b와 w로 이루어진 길이 9인 문자열이 주어진다. 이 글자들 사이에는 빈칸이 없다. 이들은 차례로 1,2,3,4,5,6,7,8,9에 해당하는 칸의 색을 나타내는데, b는 검은색이고, w는 흰색이다.
출력출력은 표준 출력이다. 각 테스트 케이스의 X에 대해 자기가 계산한 회수를 한 줄에 하나씩 출력한다. 모두 흰색으로 바꾸는 것이 불가능하면 -1을 출력한다. T개의 테스트 케이스를 모두 맞춰야 맞춘 것이다.
입력의 예~cpp 3 wbbwbbwww wwwwwwwww bwbbwbwbb
입력의 예에 대한 출력
~cpp 1 0 2