[Hard] MeetInTheMaze

(F, R, L) 의 모든 쌍을 순회하면서 세 위치가 정해졌을 때, 이동거리 합이 최소가 되는 위치를 구하면 답을 구할 수 있긴 하다. 하지만 쌍의 개수가 매우 많아서 시간내에 계산할 수 없다. |F| <= 20, |R| <= 20 인 것을 보면 (F, R) 쌍을 모두 순회하는 것은 reasonable 해 보인다. 풀이를 만들어보자. F와 R의 위치가 정해졌다. 이제 남은 것은 모든 L들과의 처리이다. 여기서 문제를 살짝 비틀어보자. F, R, L 이 모두 이동하여 어느 점에서 만나는게 아니라 F와 R이 먼저 어느 점에서 만난 후 둘이 합체한다. 그리고 합체한 채로 L에게 이동하는 것을 생각해보는 것이다. 이건 원래 문제와 완전히 같다. 이렇게 하면 단순한 최단거리 문제로 변환할 수 있다. F와 R이 만나는 거리를 알기 위해 우선 F의 위치에서 모든 칸으로 bfs, R의 위치에서 모든 칸으로 bfs를 한번 돌린다. 그럼 각 칸마다 (F의 이동거리) + (R의 이동거리) 값을 알 수 있다. 가상의 슈퍼노드를 만들고 각 칸까지 저 값을 가중치로 하는 간선을 이어준다. 인접한 칸 사이에는 가중치 1인 간선을 이어준다. 이 그래프에서 슈퍼노드를 시작으로 모든 점 까지의 최단거리를 구한다. 이렇게 되면 L이 있는 칸까지의 최단거리는 결국 셋이서 만나는 이동거리 합의 최소값이 된다. 이 값을 누적하여 답을 구하는데 쓰면 된다. 최단거리를 구할 때는 그냥 dijkstra를 쓸 수도 있고 조금 영리하게 구현하면 bfs를 쓸 수도 있다.