페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#1033
스페셜 저지

회로배치 1초 128MB

문제

회로를 n \times n의 격자 판에 배치하려고 한다. 

여기서 각 격자(정사각형 칸)는 가장자리에 있는 격자를 제외하고 상 하 좌 우 4개의 이웃 격자를 갖는다. 

회로는 시작과 끝이 있는 연속된 이웃 격자들의 길(path)이다. 

아래 그림에서는 X와 Y,\ P와 Q를 연결한 두 개의 회로가 있다. 

이미 회로들이 배치되어 있는 격자 판에 새로 배치할 회로의 양 끝 격자가 주어져 있을 때, 

이들 두 격자를 잇는 새로운 회로를 배치하려고 한다.

 

새로 배치될 회로는 이미 회로가 배치된 격자 위에 배치될 수도 있다. 

이 회로의 배치 비용은 이 회로가 지나는 격자에 따라 다음과 같이 결정된다. 

회로가 배치되지 않은 빈 격자를 지나는 비용은 1이고, 

이미 회로가 놓여있는 격자를 지날 때는 비용이 k(k≥2)이다. 

주어진 문제는 최소의 비용이 소요되는 새로운 회로를 찾는 것이다.

 

예를 들어 아래의 그림에서 k가 4로 주어진다면, 

점선을 따라 격자 A와 B를 잇는 회로의 비용은 19이지만 비용이 16인 최소비용 회로가 존재한다.

(이 비용에는 A\ B의 비용도 포함된다.)


입력

입력의 첫째 줄에는 격자 판의 크기를 나타내는 정수 n이 주어진다. (1≤n≤50)

둘째 줄에는 새로 배치할 회로의 시작 격자, 마지막 격자의 위치를 나타내는 4개의 정수가 주어진다. 한 격자의 위치는 위 그림에서 주어진 행과 열의 번호 순서로 주어진다. (시작 격자와 마지막 격자의 위치는 같을 수 없고, 이미 배치된 회로와 겹칠 수 없다.) 

셋째 줄에는 회로가 배치된 격자를 지나는데 드는 비용인 정수 k가 주어진다. (2 \le k \le 100)

넷째 줄에는 이미 배치된 회로의 개수가 주어진다. 

다섯째 줄부터는 한 줄에 한 회로의 배치 정보가 다음과 같이 주어진다. 

첫째 정수는 회로의 시작 격자, 90°로 꺾이는 방향 전환 격자들 그리고 마지막 격자의 총 개수이고,

그 다음부터는 이들 격자의 위치가 시작 격자부터 마지막 격자까지 행과 열의 순서대로 주어진다.


출력

첫째 줄에는 회로의 최소 비용을 출력한다. 

둘째 줄에는 최소 비용 회로의 정보를 다음과 같이 출력한다.

(입력 형식과 동일함) 처음에 회로의 시작 격자, 90°로 꺾이는 방향 전환 격자들, 그리고 마지막 격자의 총 개수를 출력한다. 

그 다음부터는 이들 격자의 위치를 시작 격자부터 마지막 격자까지 행과 열의 순서대로 한 개씩 공백을 두고 출력한다.


예제1

입력
11

2398

4

2

33934104

492727757
출력
16

3232898

출처

KOI 전국 1999 중2

역링크