백준 4179번 불! C++

문제

www.acmicpc.net/problem/4179

4179번: 불!

코드

#include<bits/stdc++.h>

using namespace std;

const int INF = 987654321;
char _map[1004][1004];
int n, m, sx, sy, dx[4] = { 0, 1, 0,-1 }, dy[4] = { -1, 0, 1, 0 }, ret;
int fire_check[1004][1004], person_check[1004][1004];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;

	queue<pair<int, int>> q;
	fill(&fire_check[0][0], &fire_check[0][0] + 1004 * 1004, INF);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> _map[i][j];
			if (_map[i][j] == 'F')
			{
				//불의 첫 시작 지점을 visited걸고
				fire_check[i][j] = 1;
				//q.push 한다.
				q.push({ i,j });
			}
			if (_map[i][j] == 'J')
			{
				//지훈이 bfs 시작지점
				sy = i;
				sx = j;
			}
		}
	}

	//불 최단거리
	while (!q.empty()) 
	{
		//해당 현재 q를 pop 하고
		//현재 q와 이어진 4가지 정점을 체크해야한다.
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) 
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			//범위 체크
			if ((1 <= ny && ny <= n && 1 <= nx && nx <= m) == false)
				continue;

			//방문한 정점이거나 벽이면 continue
			if (fire_check[ny][nx] != INF || _map[ny][nx] == '#') 
				continue;

			//불이 갈 수 있는 곳까지 도달했으니 
			//방문 체크를 해주고
			//q.push
			fire_check[ny][nx] = fire_check[y][x] + 1;
			q.push({ ny, nx });
		}
	}

	//지훈이가 있는 곳 방문처리하고
	//q.push
	person_check[sy][sx] = 1;
	q.push({ sy,sx });
	while (!q.empty()) 
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		//지훈이가 가장자리에 도달했다면
		//불에 타지않고 빠져나왔다는 말
		if (x == m || y == n || x == 1 || y == 1) 
		{
			//최단거리
			ret = person_check[y][x];
			break;
		}

		for (int i = 0; i < 4; i++) 
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if ((1 <= ny && ny <= n && 1 <= nx && nx <= m) == false)
				continue;

			//이미 방문했거나 벽이면 continue
			if (person_check[ny][nx] || _map[ny][nx] == '#') 
				continue;

			//불의 최단거리보다 지훈이의 최단거리가 같거나 크면 탈출할 수 없는
			//지점이니까 continue
			if (fire_check[ny][nx] <= person_check[y][x] + 1) 
				continue;

			//이동할 수 있는 곳까지 도달했으니
			//visited 해주고
			//q.push
			person_check[ny][nx] = person_check[y][x] + 1;
			q.push({ ny, nx });
		}
	}

	if (ret != 0) 
		cout << ret << "\n";
	else 
		cout << "IMPOSSIBLE \n";
	return 0;
}

걸린 시간

2시간