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

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

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

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

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

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

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

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

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

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

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

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

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

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

회로배치 timer 1초 memory 128MB

회로배치 1초 128MB