소년해방전선

개강 첫 시간 부터 과제를 내주셔서 아주 상큼하게 주말을 헌납했습니다.
종천이 아니더라도 코딩할 거리를 만들어주시네요.
어찌어찌 풀긴 풀었는데, 소스가 매우 지저분 합니다. 900줄 가까우니 원... -_-
제가 만든 예시에서는 잘 동작하는데, 다른 입력에 대해서는 장담못합니다.
기본 점수라도 주시겠죠뭐.

또 하나 내주셨는데, 열심히 파봐야겠죠. 주당 하나씩 프로그래밍 과제가 나올듯 합니다.
왠지 최악이라는... -_-
중간, 기말 고사는 프로그래밍인데, 7시간동안 본다네요. 하핫;
-------------------------------------------------------------------------------
문제
  회로를 n X n의 격자 판에 배치하려고 한다. 여기서 각 격자(정사각형 칸)는 가장자리에 있는 격자를 제외하고 상, 하, 좌, 우 4개의 이웃 격자를 갖는다. 회로는 시작과 끝이 있는 연속된 이웃 격자들의 길(path)이다. 아래 그림에서는 X와 Y, P와 Q를 연결한 두 개의 회로가 있다. 이미 회로들이 배치되어 있는 격자 판에 새로 배치할 회로의 양 끝 격자가 주어져 있을 때, 이들 두 격자를 잇는 새로운 회로를 배치하려고 한다.
  새로 배치될 회로는 이미 회로가 배치된 격자 위에 배치될 수도 있다. 이 회로의 배치 비용은 이 회로가 지나는 격자에 따라 다음과 같이 결정된다. 회로가 배치되지 않은 빈 격자를 지나는 비용은 1이고, 이미 회로가 놓여있는 격자를 지날 때는 비용이 k(k≥2) 이다. 주어진 문제는 최소의 방향 전환 격자를 가지면서 최소의 비용이 소요되는 새로운 회로를 찾는 것이다.
  예를 들어 아래의 그림에서 k가 4로 주어진다면, 점선을 따라 격자 A와 B를 잇는 회로의 비용은 19이지만, 비용이 16인 최소비용 회로가 존재한다. (이 비용에는 격자 A, B의 비용도 포함된다.)

입력형식
 입력 파일명은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에는 격자 판의 크기를 나타내는 정수 (2≤n≤50)가 주어진다. 둘째 줄에는 새로 배치할 회로의 시작 격자, 마지막 격자의 위치를 나타내는 4개의 정수가 주어진다. 한 격자의 위치는 위 그림에서 주어진 행과 열의 번호 순서로 주어진다. (시작 격자와 마지막 격자의 위치는 같을 수 없다.) 셋째 줄에는 회로가 배치된 격자를 지나는 데 드는 비용인 정수 k가 주어진다. 넷째 줄에는 이미 배치된 회로의 개수가 주어진다. 다섯째  줄부터는 한 줄에 한 회로의 배치 정보가 다음과 같이 주어진다. 첫째 정수는 회로의 시작 격자,  90°로 꺾이는 방향 전환 격자들, 그리고 마지막 격자의 총 개수이고, 그 다음부터는 이들 격자의 위치가 시작 격자부터 마지막 격자까지 행과 열의 순서대로 주어진다.

출력형식
 출력 파일명은 OUTPUT.TXT로 한다. 첫째 줄에는 회로의 최소 비용을 출력한다. 둘째 줄에는 최소비용 회로의 정보를 다음과 같이 출력한다. (입력 형식과 동일함.) 처음에 회로의 시작 격자, 90°로 꺾이는 방향 전환 격자들, 그리고 마지막 격자의 총 개수를 출력하고, 그 다음부터는 이들 격자의 위치를 시작 격자부터 마지막 격자까지 행과 열의 순서대로 한 개씩 공백을 두고 출력한다.

입력과 출력의 예
 앞 그림에 해당되는 입력과 출력은 다음과 같다.
입력(INPUT.TXT)

출력(OUTPUT.TXT)

주의사항
1. 파일 이름은 CIRCUIT.CPP, 보고서 파일은 nameCIRCUIT.hwp로 하고, 최소 비용을 구하지 못하는 경우는 0점으로 처리되며, 중간 점수도 없다.  제한시간은 10초이다.
2. 다양한 시나리오를 구성하여 n의 크기를 증가시키면서 입력 파일을 3 개 이상 만들어 수행시켜본 후 그 결과를 분석하고, 입력 파일도 제출 한다.