3701번 - 스도쿠 변형 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 32 | 7 | 6 | 28.571% |
문제
상근이는 매일 아침 신문에 나와있는 스도쿠 퍼즐을 풀면서 희망찬 아침을 시작한다. 어느 날, 퍼즐을 풀다보니 무엇인가 이상한 점을 눈치챘다. 풀고있는 퍼즐이 어제 풀었던 퍼즐을 90도 회전시킨 퍼즐이었기 때문이다. 상근이는 엄청난 배신감을 느꼈다. 물론 퍼즐을 풀기 시작할 때는 이 퍼즐이 어제 풀었던 퍼즐인지 알 수가 없다. 하지만, 점점 숫자를 채우다 보니 알게된 것이었다.
.png)
스도쿠 보드는 9×9개의 칸으로 이루어져 있다. 또, 3×3개의 칸은 3×3개의 구역(region)으로 묶여있다. 칸의 일부는 1과 9사이의 숫자로 채워져 있으며, 나머지 칸은 모두 비어있다. 퍼즐의 목표는 비어있는 칸을 1부터 9까지의 숫자로 채워서, 모든 행, 열, 구역에 1부터 9까지 숫자가 딱 한 번씩만 등장하게 하는 것이다. 올바른 스도쿠 퍼즐은 비어있는 칸을 채우는 방법이 항상 한 가지이다.
상근이는 매우 분노해 매일 밤을 술로 지새웠다. 상근이는 더 이상 신문사의 횡포에 당할 수 없다고 생각했다. 그는 오늘 퍼즐이 어제 퍼즐을 간단한 연산을 통해 만든 것인지 아닌지를 확인해보려고 한다.
허용되는 간단한 연산은 아래와 같다.
- 퍼즐 전체를 시계방향이나 반시계방향으로 회전시킨다.
- 3×9 크기의 열 세그먼트를 교환한다.
- 9×3 크기의 행 세그먼트를 교환한다.
- 행 또는 열 전체를 교환한다.
- 1부터 9까지 숫자로 이루어진 순열 f를 모든 칸에 적용한다. (즉, 모든 칸의 x를 f(x)로 바꾸는 것)
위의 모든 연산은 스도쿠의 정답에 적용하며, 변환 전에 풀 수 있었던 스도쿠는 변환 후에도 풀 수 있다.
입력
첫째 줄에 테스트 케이스의 개수 N이 주어진다. (0 ≤ N ≤ 50)
테스트 케이스의 처음 9개 줄은 어제 퍼즐의 정답이며, 다음 9개 줄은 오늘 퍼즐이다. 비어있는 칸은 0으로 주어진다.
각 테스트 케이스의 사이에는 빈 줄이 하나씩 주어진다. 어제 퍼즐은 항상 올바른 스도쿠이며, 오늘 퍼즐의 정답도 항상 한 가지이다.
출력
각 테스트 케이스에 대해서, 오늘 퍼즐이 어제 퍼즐의 변형이면 Yes를 아니면 No를 출력한다.
예제 입력 1
2 963174258 178325649 254689731 821437596 496852317 735961824 589713462 317246985 642598173 060104050 200000001 008305600 800407006 006000300 700901004 500000002 040508070 007206900 534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179 010900605 025060070 870000902 702050043 000204000 490010508 107000056 040080210 208001090
예제 출력 1
Yes No
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2006 A번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호