시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 144 | 92 | 74 | 62.185% |
ACM-ICPC 리저널 대회가 열리기 전, 현장 담당관과 자원봉사자들은 매우 바쁘다.
그들의 임무 중 하나는 대회장의 테이블을 적절히 배치하여 인접한 두 테이블에는 서로 다른 학교 출신의 팀이 앉도록 하는 것이다.
이 일은 상당히 힘든 일이기 때문에 일반적으로 사람이 직접 하기보다는 프로그램을 통해 수행한다. 올해는 심사위원들이 이 일을 맡게 되었다.
심사위원들은 프로그램을 통해 자리 배치를 끝냈다. 그 후 가만히 생각해보니, 이 자리 배치 문제가 대회 문제로 상당히 좋을 것 같았다. 따라서 심사위원들은 이 문제의 일부를 실제 대회 문제로 출제하기로 하였다.
심사위원들의 프로그램 작동 방식은 아주 단순하다. 우선 그냥 임의로 자리를 배치시킨다. 이후 어떤 인접한 두 자리에 같은 대학 출신의 두 팀이 앉게 되는지 확인한다. 만일 그러한 자리가 존재한다면 그러한 배치로 혜택을 받는 학교, 즉 인접한 자리에 같은 학교 출신 팀이 앉게 되는 학교가 총 몇 개인지 센다.
대회장은 2차원 평면에 N개의 행, M개의 열로 이루어진 표로 나타낼 수 있다.
표의 각 칸에는 한 팀이 앉거나 아무 팀도 앉지 않는다.
각 팀은 최대 8개의 인접한 팀을 가질 수 있다. 만일 자리가 모서리 쪽이라거나, 주변에 빈 자리가 있는 경우엔 8개 미만의 인접한 팀을 갖게 된다.
예를 들어 위와 같은 상황에서, 팀 E는 7개의 인접한 팀 A, B, C, D, F, G, H를 갖는다.
또한 팀 A는 3개의 인접한 팀 B, D, E를 갖는다.
첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 100 )
각 테스트 케이스의 첫 줄엔 대회장의 세로 길이와 가로 길이 N, M이 주어진다. ( 1 ≤ N, M ≤ 100 )
이어 N줄에 걸쳐 M개의 정수로 각 자리에 어떤 팀이 앉게 되는지가 주어진다. 팀의 ID는 1부터 100까지의 정수로 표현되며, 만일 ID가 -1로 주어진다면 그 자리가 비어있음을 의미한다.
각 테스트 케이스마다, 인접한 같은 학교 출신의 팀을 가지는 학교가 총 몇 개인지 출력한다.
3 3 3 1 2 3 2 2 2 1 1 1 3 3 1 2 3 3 -1 1 2 -1 2 3 3 1 2 3 -1 1 5 1 2 4
2 0 1
ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2012 Arab Collegiate Programming Contest I번