BOJ-9376脱獄(C++)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <deque>
#define INF 987654321

using namespace std;

int dist[103][103][3];
bool ch[103][103][3];
int dy[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
vector<string> arr;

void checkDoor(int x, int y, int H, int W,int type) {
	deque<pair<int, int>> dq;
	dq.push_front({ x,y });
	ch[x][y][type] = true;
	while (!dq.empty()) {
		x = dq.front().first;
		y = dq.front().second;
		dq.pop_front();
		for (int k = 0; k < 4; k++) {
			int nx = x + dy[k][0];
			int ny = y + dy[k][1];
			if (nx < 0 || ny < 0 || nx >= H + 2 || ny >= W + 2 || ch[nx][ny][type] || arr[nx][ny] == '*') continue;
			ch[nx][ny][type] = true;
			if (arr[nx][ny] == '.' || arr[nx][ny] == '$') {
				dist[nx][ny][type] = dist[x][y][type];
				dq.push_front({ nx,ny });
			}
			else if (arr[nx][ny] == '#') {
				dist[nx][ny][type] = dist[x][y][type] + 1;
				dq.push_back({ nx,ny });
			}
		}
	}
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		memset(dist, 0, sizeof(dist));
		memset(ch, false, sizeof(ch));
		int h, w;
		cin >> h >> w;
		string str = "";
		pair<int, int> p[2];
		int idx = 0;
		for (int i =0; i < w+2; i++) {
			str += ".";
		}
		arr.push_back(str);
		for (int i = 0; i < h; i++) {
			cin >> str;
			str = "." + str;
			str += ".";
			arr.push_back(str);
		}
		str = "";
		for (int i = 0; i < w+2; i++) {
			str += ".";
		}
		arr.push_back(str);
		for (int i = 1; i < h + 1; i++) {
			for (int j = 1; j < w + 1; j++) {
				if (arr[i][j] == '$') p[idx++] = { i,j };
			}
		}
		checkDoor(0, 0, h, w, 0);
		checkDoor(p[0].first, p[0].second, h, w, 1);
		checkDoor(p[1].first, p[1].second, h, w, 2);
		int res = INF;
		for (int i = 0; i < h+2; i++) {
			for (int j = 0; j < w + 2; j++) {
				if (arr[i][j] == '*') continue;
				int sum = 0;
				for (int k = 0; k < 3; k++) {
					sum += dist[i][j][k];
				}
				if (arr[i][j] == '#') sum -= 2;
				res = min(sum, res);
			}
		}
		cout << res << "\n";
		arr.clear();
	}
	return 0;
}