백준 5427번 C++

#include <iostream>
#include <cstring>
#include <queue>
#include <string>

using namespace std;
int const MAX = 1000;
int w, h;
string map[MAX];
vector<pair<int, int>> firecopy;
pair<int, int> location;
int visited[MAX][MAX];
struct Move {
	int x, y;
};
Move mv[4] = { {-1,0},{1,0},{0,1},{0,-1} };

bool exitcheck(int i, int j) {
	if (i == 0 || i == h - 1 || j == 0 || j == w - 1)
		return true;
	else
		return false;
}

int bfs() {
	int day = 0;
	queue<pair<int, int>> loc;
	loc.push(location);
	queue<pair<int, int>> fire;
	for (int i = 0; i < firecopy.size(); i++)
		fire.push(firecopy[i]);

	while (!loc.empty()) {
		int firesize = fire.size();
		for (int index = 0; index < firesize; index++) {
			int i = fire.front().first;
			int j = fire.front().second;
			fire.pop();

			for (int k = 0; k < 4; k++) {
				int movei = i + mv[k].x;
				int movej = j + mv[k].y;

				if (movei >= 0 && movei < h && movej >= 0 && movej < w) {
					if (map[movei][movej] == '.' || map[movei][movej] == '@') {
						map[movei][movej] = '*';
						fire.push(make_pair(movei, movej));
					}
				}
			}
		}

		int locationsize = loc.size();
		for (int index = 0; index < locationsize; index++) {
			int i = loc.front().first;
			int j = loc.front().second;
			loc.pop();

			if (exitcheck(i,j))
				return day + 1;

			for (int k = 0; k < 4; k++) {
				int movei = i + mv[k].x;
				int movej = j + mv[k].y;

				if (movei >= 0 && movei < h && movej >= 0 && movej < w) {
					if (visited[movei][movej] == -1 && map[movei][movej] == '.') {
						loc.push(make_pair(movei, movej));
						visited[movei][movej] = 1;
					}
				}
			}
		}
		day++;
	}
	return -1;
}

int main(void) {
	int testcase,answer;

	cin >> testcase;
	for (int i = 0; i < testcase; i++) {
		cin >> w >> h;
		memset(visited, -1, sizeof(visited));
		firecopy.clear();
		for (int j = 0; j < h; j++) {
			cin >> map[j];
			for (int k = 0; k < w; k++) {
				if (map[j][k] == '@')
					location = make_pair(j, k);
				if (map[j][k] == '*')
					firecopy.push_back(make_pair(j, k));
			}
		}

		answer = bfs();
		if (answer == -1)
			cout << "IMPOSSIBLE" << endl;
		else
			cout << answer << endl;
	}
	return 0;
}