광자포 건설 timer 1s memory 256MB

코파룰루 은하계에서는 인정머리 없는 괴물 종족인 자그(zag)족이 살고 있다. 자그족은 수많은 괴물들을 부화시켜서 대규모 군대를 만들어 인해전술을 사용한다. 따라서 자그족의 공격에 살아남으려면 방어시설이 필요하다. 포르토스(portoss)족은 광자포라는 방어시설을 사용하는데, 광자포를 한 장소에 집중적으로 지으면, 그 장소에서는 제 아무리 자그족이라도 방어선을 건드리지도 못하고 전멸해버린다.

현재 광자포들은 좌표평면 위에 지어져 있으며, 모두 이어져 있다. 모두 이어져 있다는 것은, 상하좌우가 인접하면 붙어 있는 것이라고 할 때, 모든 광자포들이 직접, 또는 다른 붙어있는 광자포를 경유해서 붙어 있다는 것이다. 또한, 광자포가 없는 빈 땅덩어리들 역시 모두 이어져 있다.

광자포는 발전소이자 에너지원인 수정탑이 없으면 동력이 끊겨 작동하지 않는다. 그런데 자그족의 괴물 군사가 용맹하게 돌진해서 수정탑을 부셔버렸다. 모든 광자포의 동력이 끊겨서 포르토스족이 위기에 처했을 때, 포르토스의 한 과학자는 자신을 “차원 장인”이라고 칭하면서 다음을 제안했다.

자신이 한 광자포에 위치해 있을 때, 그 주변 몇 개정도의 광자포는 작동시킬 수 있다고 한다. 그래서 임시적으로 그 부근은 방어할 수 있다는 것이다. 그러나, 자그족의 공격 방향에 따라 자기가 광자포에서 다른 광자포로 이동해서 동력 공급을 해야 하는데, 이 때 자신은 너무 중요한 임무를 맡고 있으므로 인접한 광자포를 통해서만 이동하겠다고 한다. 빈 땅으로 이동하면 자신이 자그족의 공습을 받을 수도 있기 때문이다. 이 때 이동거리를 최소화 시킬 수 있도록, 어느 광자포에서 다른 광자포로 움직일 때든지, 맨하탄 최단거리로만 이동하고 싶다고 한다. 그러려면 몇 개의 광자포를 더 지어야 한다고 한다.

맨하탄 최단거리는 (x1, y1)에서 (x2, y2)로 이동하는 거리가 |x1-x2| + |y1-y2|일 때 맨하탄 최단거리라고 말한다.

예를 들어 다음과 같이 광자포가 지어져 있다. P는 광자포를 뜻하며, O는 빈 땅이다.

OOOOOOOO

OPPPPPOO

OPOOOOOO

OPPPPPOO

OOOOOOOO

이 경우 (2, 6)에서 (4, 6)으로 차원장인이 광자포만 통해서 이동하기 위해서는 'ㄷ'자 형태로 돌아가야 한다. (2, 3)에서 (4, 4)로 이동하는 것도 마찬가지이다. 따라서 (3, 3), (3, 4), (3, 5), (3, 6)에 추가 광자포를 지어야만 어느 광자포에서든지 맨하탄 최단거리로 다른 광자포로 이동할 수 있다.

광자포들의 위치가 주어질 때, 차원 장인이 맨하탄 최단거리로만 움직일 수 있도록 추가로 건설해야 하는 광자포의 최소 개수를 구하는 프로그램을 작성하라.