1896번 - 파급효과 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 28 | 17 | 17 | 73.913% |
문제
파급효과가 가능한 퍼즐인지 판별하여라.
파급효과는 여러개의 폴리오미노로 구성된 직사각형의 그리드에서 발생한다. 폴리오미노는 하나 이상의 같은 크기의 정사각형을 이어붙여 만든 도형이다.
우리는 그리드 안의 모든 칸에 자연수를 배치해야한다. 이때 다음과 같은 규칙을 따르며, 일부 자연수는 미리 주어질 수 있다.
- 1 ~ (폴리노미오 안의 칸 수) 의 자연수들은 해당 폴리노미오 안에 반드시 한번씩만 배치되어야 한다.
- 하나의 줄이나 행에 동일한 숫자가 배치되기 위해선 두 숫자 사이에 해당 숫자만큼의 다른 칸이 존재해야 한다.
예를 들어, '1'이 배치된 칸은 서로 인접할 수 없으며, 다른 숫자가 쓰여진 칸이 두 '1' 사이에 하나 이상 존재해야 한다.
같은 줄이나 행에 '3'이 배치되기 위해선 다른 숫자가 쓰여진 칸이 사이에 세개 이상 존재해야 한다.
이 문제에서 폴리노미오의 크기는 최대 8이다.
입력
입력의 첫째 줄에는 테스트 케이스 T가 주어진다. (T<=100)
각각의 테스트 케이스의 첫째 줄에는 두 정수 R, C 가 주어진다. (4<=R, C<=15)
이후 R개 줄에는 그리드에 쓰여진 숫자들을 나태는 C개의 숫자 d_i로 구성된 문자열이 입력된다. (1<=d_i<=8)
이후 R개 줄에는 퍼즐의 각 칸이 폴리노미오로 연결된 방향을 나타내는 C개의 숫자가 입력된다. (이는 RxC 의 테이블이며, 이를 "descr" 라고 하자. 0<=descr(r,c)<=15)
descr(r,c)의 값은 이웃된 칸과의 연결 여부에 따라 다음과 같이 결정된다.
descr(r,c)=0 if(connected((r,c),(r-1,c)) descr(r,c)+=1; (UP) if(connected((r,c),(r,c+1)) descr(r,c)+=2; (RIGHT) if(connected((r,c),(r+1,c)) descr(r,c)+=4; (DOWN) if(connected((r,c),(r,c-1)) descr(r,c)+=8; (LEFT)
예를 들어, 크기가 1인 폴리노미오의 칸은 주변의 어떠한 칸과도 이어져있지 않으므로 0의 값을 가지며, 위쪽의 칸과 아래의 칸에 이어져있는 칸들은 5의 값을 가지게 된다.
출력
각각의 테스트 케이스에 대해 한 "valid" 또는 "invalid" 를 출력하여라.
예제 입력 1
2 6 6 241321 312432 131243 423121 214312 141231 2 12 4 4 6 8 4 5 1 5 5 4 5 1 0 5 1 5 3 8 4 1 4 1 2 10 9 2 9 4 0 2 10 10 8 1 6 6 421321 312432 131243 423121 214312 141231 2 12 4 4 6 8 4 5 1 5 5 4 5 1 0 5 1 5 3 8 4 1 4 1 2 10 9 2 9 4 0 2 10 10 8 1
예제 출력 1
valid invalid
출처
ICPC > Regionals > North America > Rocky Mountain Regional > Alberta Collegiate Programming Contest > ACPC 2012 D번
- 문제를 번역한 사람: jb_cubedr
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호