백준 알고리즘(C++)

백준 4179번 불! ( C++ )

coding232624 2024. 4. 1. 16:46

문제

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

 

4179번: 불!

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자

www.acmicpc.net

 

해설

설명이 부족했던 문제..

불이 여러개라는 점을 잘 파악해야하며

정해진 맵 밖으로는 불이 퍼지지 않는다는점에 유의해서 코드를 작성해야함

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
 
int r, c, visited[1004][1004], fireLocation[1004][1004], startX, startY, ret;
char mp[1004][1004];
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
bool flag = false;
vector<pair<int, int>> fire;
 
void bfs(int y, int x)
{
  visited[y][x] = 1;
  queue<pair<int, int>> q;
  q.push({y, x});
  while (q.size())
  {
    tie(y, x) = q.front();
    q.pop();
    for (int i = 0; i < 4; i++)
    {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if ((visited[y][x] + 1) >= fireLocation[ny][nx] && fireLocation[ny][nx] != 0)
      {
        continue;
      }
      if (nx == 0 || ny == 0 || nx == c - 1 || ny == r - 1)
      {
        if (mp[ny][nx] == '.')
        {
          cout << visited[y][x] + 1;
          flag = true;
          return;
        }
      }
      if (nx < 0 || ny < 0 || nx >= c || ny >= r || visited[ny][nx] || mp[ny][nx] == '#' || mp[ny][nx] == 'F')
        continue;
      visited[ny][nx] = visited[y][x] + 1;
      q.push({ny, nx});
    }
  }
}
 
void checkFireLocation(int y, int x)
{
  fireLocation[y][x] = 1;
  queue<pair<int, int>> q;
  q.push({y, x});
  while (q.size())
  {
    tie(y, x) = q.front();
    q.pop();
 
    for (int i = 0; i < 4; i++)
    {
      int nx = x + dx[i];
      int ny = y + dy[i];
 
      if (nx < 0 || ny < 0 || nx >= c || ny >= r || (fireLocation[ny][nx] && fireLocation[ny][nx] <= (fireLocation[y][x] + 1)) || mp[ny][nx] == '#' || mp[ny][nx] == 'F')
        continue;
      fireLocation[ny][nx] = fireLocation[y][x] + 1;
      q.push({ny, nx});
    }
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> r >> c;
  for (int i = 0; i < r; i++)
  {
    for (int j = 0; j < c; j++)
    {
      cin >> mp[i][j];
      if (mp[i][j] == 'J')
      {
        startX = j;
        startY = i;
      }
      else if (mp[i][j] == 'F')
      {
        fire.push_back({i, j});
      }
    }
  }
 
  for (pair<int, int> fi : fire)
  {
    checkFireLocation(fi.first, fi.second);
  }
 
 
 
  if (startX == 0 || startY == 0 || startX == c - 1 || startY == r - 1)
  {
    cout << 1;
    return 0;
  }
  bfs(startY, startX);
  if (!flag)
  {
    cout << "IMPOSSIBLE";
  }
}
 cs