백준 5427 : 불

www.acmicpc.net/problem/5427

5427번: 불

백준 4179 - 불! 과 동일한 문제다. 날먹해주자.

 

unfunhy.tistory.com/15

백준 4179 - 불!

다른 점은 테케가 여러개라는 것 뿐이다. 테케가 여러개이므로 변수 초기화 작업이 필요해서 두 개의 큐를 지역변수로 선언하고 BFS함수에 참조형 매개변수로 넘겨줬다.

 

#include <iostream>
#include <queue>
#include <string>
#include <tuple>

using namespace std;

typedef tuple<int, int, int> t;

int R, C;
bool visited[1000][1000];

void bfs(queue<t>& q, queue<t>& fq) {
	int x, y, fx, fy, cnt, fcnt, nx, ny, min_val = 1e9;
	int dx[] = { -1,1,0,0 };
	int dy[] = { 0,0,-1,1 };

	while (!q.empty()) {
		tie(x, y, cnt) = q.front();
		q.pop();

		if (x == 0 || y == 0 || x == C - 1 || y == R - 1) {
			min_val = cnt;
			break;
		}
		while (!fq.empty()) {
			tie(fx, fy, fcnt) = fq.front();
			if (fcnt != cnt) break;
			fq.pop();

			for (int k = 0; k < 4; k++) {
				nx = fx + dx[k]; ny = fy + dy[k];
				if (nx < 0 || nx >= C || ny < 0 || ny >= R || visited[ny][nx]) continue;
				fq.emplace(nx, ny, fcnt + 1);
				visited[ny][nx] = 1;
			}
		}

		for (int k = 0; k < 4; k++) {
			nx = x + dx[k]; ny = y + dy[k];
			if (nx < 0 || nx >= C || ny < 0 || ny >= R || visited[ny][nx]) continue;
			q.emplace(nx, ny, cnt + 1);
			visited[ny][nx] = 1;
		}
	}

	if (min_val != 1e9) cout << min_val << '\n';
	else cout << "IMPOSSIBLE\n";
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	string tmp;

	cin >> N;
	while (N--) {
		queue<t> fq;
		queue<t> q;
		cin >> C >> R;
		for (int j = 0; j < R; j++) {
			cin >> tmp;
			for (int i = 0; i < C; i++) {
				if (tmp[i] == '@') {
					q.emplace(i, j, 1);
					visited[j][i] = 1;
				}
				else if (tmp[i] == '*') {
					fq.emplace(i, j, 1);
					visited[j][i] = 1;
				}
				else if (tmp[i] == '#') {
					visited[j][i] = 1;
				}
			}
		}
		bfs(q, fq);
		for (int j = 0; j < R; j++) {
			for (int i = 0; i < C; i++) {
				visited[j][i] = 0;
			}
		}
	}

	return 0;
}

메모리: 6156 kb

시간: 40 ms