격자TSP timer 1s memory 128MB

N 행 M열로 구성된 2차원 격자가 있다. 격자는 일정한 간격을 두고 사각형의 형태로 점이 배치된 형태를 뜻한다. 

처음의 점을 (0,0)이라고 하고, 임의의 한 점을 (i,j)라고 할 경우, 이는 처음의 점에서 세로로 i의 길이만큼, 가로로 j의 길이만큼 떨어진 점을 뜻한다.

원점(처음의 점)으로 부터 시작하여 각 점을 한 번씩만 거친 다음 다시 원점으로 되돌아오는 경로 중 가장 짧은 경로를 찾고자 한다. 

모든 점간이 이동을 할 수 있는 것은 아니며, (i, j)에서는 (i±1, j), (i, j±1), (i±1, j±1)로 이동이 가능한데,

아래의 그림은 2행 3열의 경우의 가장 짧은 경로의 예를 그림으로 표현한 것이다. 

이 경우에는 6의 비용이 소요되게 된다.