문제
뒤집기(Inverso) 게임은 3 ×3 격자 위에서 하는 게임이다.
각 격자는 검정 또는 흰색이 칠해져 있다.
그리고 각각의 격자는 다음 그림과 같이 숫자가 매겨져 있다.
게임을 하는 사람은 하나의 격자를 선택하여 그 격자의 색을 바꿀 수 있다.
이때 그 격자와 인접한 모든 격자의 색을 바꾸게 된다.
(검정은 흰색으로 흰색은 검정으로 바뀐다)
- 격자 1을 선택하면 1, 2, 4, 5의 색이 바뀐다
- 격자 2를 선택하면 1, 2, 3, 4, 5, 6의 색이 바뀐다.
- 격자 3을 선택하면 2, 3, 5, 6의 색이 바뀐다.
- 격자 4를 선택하면 1, 2, 4, 5, 7, 8의 색이 바뀐다.
- 격자 5는 모든 격자의 색을 바꾼다
- 격자 6은 2, 3, 5, 6, 8, 9
- 격자 7은 4, 5, 7, 8
- 격자 8은 4, 5, 6, 7, 8, 9
- 격자 9는 5, 6, 8, 9
게임의 목적은 격자 색이 주어졌을 때, 모든 격자를 흰색으로 만드는 가장 빠른 방법을 찾는 것이다.
단, 격자를 적어도 한 번 이상 바꿔야 한다.
입력
첫 행에는 게임의 횟수 N ( 0≤N≤10,000 )이 주어진다.
그 이후로 N 개의 행이 이어지는데,
각 행에는 b(검정) 혹은 w(흰색)의 문자 9 개로 이루어진 문자열이 나타나며,
이 문자열은 격자 1부터 9까지의 색을 나타낸다. 이것이 격자의 초기 색깔이다.
출력
각 행은 입력에서 주어진 문제 하나 하나에 해당하는 답을 적는다.
답은 ‘1’.‘9’의 문자로 이루어진 가장 짧은 문자열(격자를 선택하는 순서를 나타낸다)을 쓰면 된다.
만약 가장 길이가 짧은 답이 둘 이상이라면 사전식 순서로 빠른 것이 답이 된다.
즉, ‘1234’가 ‘1342’보다 더 빠르므로 ‘1234’가 답이 된다.
예제
3
bbwbwbwbw
bwwwbwbwb
bbbbwbbbw
2459
267
356789
로그인해야 코드를 작성할 수 있어요.