문제https://www.acmicpc.net/problem/9376두 명의 죄수가 $H \times W$ 크기의 감옥에 갇혀 있다.감옥을 구성하는 격자 칸은 빈 칸('.'), 벽('*'), 문('#'), 죄수('$')로 이루어져 있다.두 죄수가 모두 감옥의 바깥으로 탈출하기 위해 열어야 하는 문의 최소 개수를 구하는 문제이다.풀이문의 개수가 충분히 적다면 문의 열림/닫힘 상태를 관리하는 비트마스킹 + BFS로 해결할 수 있으나, 이 문제에서는 먹히지 않는다. 답이 나올 수 있는 경우를 두 가지로 나눠보았다.1. 두 명의 죄수가 만나지 않고 각각 탈출하는 경우각 죄수를 시작점으로 두고 다익스트라 혹은 0-1 BFS로 탈출하는 최단 경로를 구한다.2. 두 명의 죄수가 만나서 같이 탈출하는 경우첫 번째 죄수..