시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 129 | 46 | 39 | 38.614% |
4명의 여신에 의해 수호되고 있는 이(異)세계는 오늘도 여전히 신도들을 모으기 위한 전쟁이 일어나고 있다. 최근 전쟁에서 계속 패하기만 했던 여신 이나는 다음 전쟁에서는 꼭 이기리라 다짐하고 다른 여신들의 행동 패턴을 분석하였다. 결국 이나는 모든 여신들의 이동을 수치화하는데 성공했으며 이를 단위 이동이라 부르기로 했다.
단위 이동의 몇 가지 특징을 정리해보면 다음과 같다.
어떤 좌표가 주어졌을 때 단위 이동을 적당한 순서로 조합하여 도달할 수 있으면 이동 가능한 위치, 없으면 불가능한 위치라고 한다. 이때, 각 단위 이동은 몇 번이고 사용할 수 있다. 단, 최대 20억 번만 움직일 수 있다.
만약 도달 가능한 위치의 경우, 가장 적은 수의 단위 이동을 사용해 이동했을 때 사용된 단위 이동의 수를 최단 이동 횟수라고 한다. 즉, 어떤 위치로의 이동 횟수 x가 같은 위치로 움직이는 다른 모든 이동 횟수 y에 대해 x ≤ y를 만족 한다면 x는 최단 이동 횟수이다.
예를 들어 여신들이 2차원 공간에서 움직인다고 가정하자. 만약 단위 이동의 집합이 {(1, 0), (0, 1)}이라면 (2, 1)은 (1, 0)+(1, 0)+(0, 1)과 같이 표현할 수 있으므로 이동 가능한 위치이고 다른 어떤 이동보다 이보다 적은 횟수로 움직일 수 있지 않으므로 최단 이동 횟수는 3이다. 반면에 (-1, 1)로는 이동할 수 없다. 즉 단위 이동의 횟수는 항상 음이 아닌 정수여야 한다.
이나는 특정 위치가 주어졌을 때 다른 여신들이 그 위치로 움직일 수 있는지 없는지를 빠르게 판단하고, 그 위치까지 가는데 필요한 최단 이동 횟수를 계산하는 알고리즘을 설계하여 다음 전쟁 때 사용하려 한다. 하지만 할 일이 많기에 신실한 신도인 당신에게 이 일을 맡기기로 했다.
여신 이나를 도와 전쟁에서 승리하기 위한 알고리즘을 설계하자.
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 차원의 수를 나타내는 양의 정수 n(1 ≤ n ≤ 500)이 주어진다. 다음 줄부터 여신들의 단위 이동들이 n개의 줄에 걸쳐 주어진다. i번째 줄에는 i번 단위 이동을 나타내는 n개의 정수 xij(1 ≤ i ≤ n, 1 ≤ j ≤ n, -1,000 ≤ xij ≤ 1,000)가 빈칸을 사이에 두고 주어진다. 단위 이동은 처음 나오는 1의 위치가 증가하는 순서대로 주어진다. 그 다음 줄에는 특정 위치의 좌표를 나타내는 n개의 정수 yi(1 ≤ i ≤ n, -5×108 ≤ yi ≤ 5×108)가 주어진다.
각 테스트 케이스별로 한 줄에 한 개씩 다른 여신들이 주어진 특정 좌표에 도달할 수 있다면 1, 없다면 0을 출력한다. 만약 도달할 수 있다면, 같은 줄에 추가로 최단 이동 횟수를 빈칸으로 구분하여 출력한다.
3 1 1 5 2 1 0 0 1 -1 1 3 1 1 1 0 1 -1 0 0 1 1 2 0
1 5 0 1 2
University > 인하대학교 > 2015 인하대학교 프로그래밍 경시대회 E번