2564 경비원

w*h크기의 블록의 경계에 상점들이 있고, 그 어느 한 좌표에 경비원이 있다고 할 때, 경비원의 그 위치에서 각 상점까지 가는 최단거리의 합을 구하는 문제이다. 단, 경비원은 경계로만 이동해야 한다.

최단거리라고해도 사실 한 위치에서 다른 한 위치로 가는 최단거리는 이 문제에서 두가지 경우밖에 없다. 그것은 한쪽으로 가는 거리와 경계의 총 길이에서 그쪽으로 가는 거리를 빼준 거리이다. 따라서 각 상점마다 방금말한 두 거리중 작은값을 구해서 더해주면 된다.

소스