[BAE/<JOON> 문제풀이] 5427. 불

https://www.acmicpc.net/problem/5427

5427번: 불

서론

풀이 좀 그때 그때 풀자마자 써야겠다. 귀찮아서 나중에 몰아쓰니까 문제 2번푸는 기분이다.

---

풀이

불이 사람보다 먼저 퍼진다는게 가장 중요하다.

그래서 처음에 작성한 pq를 사용하는 풀이는 폐기했다. pq로는 불과 사람을 번갈아 움직이는 구현이 힘들다.

그 외에는 그냥 불 움직이고 사람 움직이고 반복하며 동일한 타일에서 겹치지 않도록만 신경쓰면 된다.

쉬운 문젠 줄 알았는데 움직이는 순서 짜는 것 때문에 너무 많이 틀렸다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <cstdlib>
using namespace std;
struct node {
	int x, y, cnt, p;
};
struct cmp {
	bool operator()(node a, node b) {
		if (a.p == 1) return false;
		if (b.p == 1) return true;
		return a.cnt > b.cnt;
	}
};
int mvx[4] = { 0, 1, 0, -1 };
int mvy[4] = { 1, 0, -1, 0 };
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int tc; cin >> tc;
	while (tc--) {
		int n, m; cin >> m >> n; vector<vector<int>> arr(n + 1, vector<int>(m + 1)), ch(n + 1, vector<int>(m + 1, 21e8));
		queue<node> q;
		vector<node> fire;
		int sx, sy;
		for (int i = 1; i <= n; i++) {
			string s; cin >> s;
			for (int j = 1; j <= m; j++) {
				if (s[j - 1] == '#') {
					arr[i][j] = 1;
				}
				if (s[j - 1] == '@') {
					ch[i][j] = 0;
					//q.push({ i, j, 0, 1 });
					sx = i; sy = j;
				}
				if (s[j - 1] == '*') {
					arr[i][j] = 666;
					fire.push_back({ i, j, 0, 666 });
				}
			}
		}
		if (sx == 1 || sx == n || sy == 1 || sy == m) {
			cout << 1 << "\n";
			continue;
		}
		for (auto f : fire) {			
			q.push(f);
		}
		q.push({ sx, sy, 0, 1 });
		int sign = 0;
		while (!q.empty()) {
			auto cur = q.front(); q.pop();
			//if (arr[cur.x][cur.y] == 666 && cur.p == 1) continue;
			for (int i = 0; i < 4; i++) {
				int mx = cur.x + mvx[i];
				int my = cur.y + mvy[i];
				if (cur.p == 1) {
					if (mx < 1 || my < 1 || mx > n || my > m) {
						cout << cur.cnt + 1 << "\n";
						sign = 1;
						break;
					}
					if (arr[mx][my] == 1 || arr[mx][my] == 666 || ch[mx][my] <= cur.cnt + 1) continue;
					ch[mx][my] = cur.cnt + 1;
					q.push({ mx, my, cur.cnt + 1, 1 });
				}
				if(cur.p == 666) {
					if (mx > n || mx < 1 || my > m || my < 1 || arr[mx][my] == 1 || arr[mx][my] == 666) continue;	
					arr[mx][my] = 666;
					q.push({ mx, my, 0, 666 });
				}
			}
			if (sign == 1) break;
		}		
		if (sign == 0) {
			cout << "IMPOSSIBLE" << "\n";
		}
	}
	return 0;
}