레이팅 미적용회로를 \(n \times n\)의 격자 판에 배치하려고 한다. 여기서 각 격자(정사각형 칸)는 범위 밖에 있는 격자를 제외하고 상, 하, 좌, 우 4개의 이웃 격자를 갖는다. 회로는 시작과 끝이 있는 연속된 이웃 격자들의 길(path)이다. 아래 그림에서는 \(X\)와 \(Y\), \(P\)와 \(Q\)를 연결한 두 개의 회로가 있다. 이미 회로들이 배치되어 있는 격자 판에 새로 배치할 회로의 양 끝 격자가 주어져 있을 때, 이들 두 격자를 잇는 새로운 회로를 배치하려고 한다.
새로 배치될 회로는 이미 회로가 배치된 격자위에 배치될 수도 있다. 이 회로의 배치 비용은 이 회로가 지나는 격자에 따라 다음과 같이 결정된다. 회로가 배치되지 않은 빈 격자를 지나는 비용은 1이고, 이미 회로가 놓여있는 격자를 지날 때는 비용이 \(k\)이다. 주어진 문제는 최소의 비용이 소요되는 새로운 회로를 찾는 것이다.
예를 들어 아래의 그림에서 \(k\)가 4로 주어진다면, 점선을 따라 격자 \(A\)와 \(B\)를 잇는 회로의 비용은 19이지만, 비용이 16인 최소비용 회로가 존재한다. (이 비용에는 \(A\), \(B\)의 비용도 포함된다.)
첫째 줄에는 격자 판의 크기를 나타내는 정수 \(n(1 \le n \le 50)\)이 주어진다.
둘째 줄에는 새로 배치할 회로의 시작 격자, 마지막 격자의 위치를 나타내는 4개의 정수가 주어진다. 한 격자의 위치는 위 그림에서 주어진 행과 열의 번호 순서로 주어진다. 시작 격자와 마지막 격자의 위치는 같을 수 없다.
셋째 줄에는 회로가 배치된 격자를 지나는데 드는 비용인 정수 \(k(2 \le k \le 60)\)가 주어진다.
넷째 줄에는 이미 배치된 회로의 개수 \(m(1 \le m \le 7)\)이 주어진다.
다섯째 줄부터는 한줄에 한 회로의 배치 정보가 다음과 같이 주어진다. 첫째 정수는 회로의 시작 격자, 90°로 꺾이는 방향 전환 격자들, 그리고 마지막 격자의 개수이다. 이 값은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 그 다음 부터는 이들 격자의 위치가 시작 격자부터 마지막 격자까지 행과 열의 순서대로 주어진다.
첫째 줄에는 회로의 최소 비용을 출력한다. 둘째 줄에는 최소비용 회로의 정보를 다음과 같이 출력한다. (입력 형식과 동일함) 처음에 회로의 시작 격자, 90°로 꺾이는 방향 전환 격자들, 그리고 마지막 격자의 총 개수를 출력한다. 그 다음부터는 이들 격자의 위치를 시작 격자부터 마지막 격자까지 행과 열의 순서대로 한 개씩 공백을 두고 출력한다.
11
2 3 9 8
4
2
3 3 9 3 4 10 4
4 9 2 7 2 7 7 5 7
16
3 2 3 2 8 9 8
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 1999 > 2차 대회 > 중등부 2번