5427번 - 불
상근이에 대한 bfs를 돌린 후 상근이가 탈출했을 때 , flag를 설정해서 while문에서 더 도는걸 막아주세요.
+ 사용한 큐 초기화 해주셔야 다음 테스트 케이스에 영향을 받지 않는다고 합니다.
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long llu; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<int, pii> piii; typedef pair<ll, ll> pll; typedef pair<ll, int> pli; typedef pair<int, ll> pil; typedef pair<string, int> psi; typedef pair<int, char> pic; #define X first #define Y second //if(nx<0||nx>=n||ny<0||ny>=m) continue; char board[1002][1002]; int dist1[1002][1002]; // 불의 전파속도 저장하는 배열 int dist2[1002][1002]; // 지훈이의 이동 저장하는 배열 int number; int w,h; // w는 열 h는 행의 수 int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); queue <pii> q1; queue <pii> q2; cin >> number; while(number--) { bool flag=false; cin >> w >> h; //h가 행. w가 열 for(int i=0;i<h;i++) { fill(dist1[i],dist1[i]+w,-1); fill(dist2[i],dist2[i]+w,-1); } for(int i=0;i<h;i++) for(int j=0;j<w;j++) cin >> board[i][j]; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(board[i][j]=='*') //불이 난 위치 { q1.push({i,j}); dist1[i][j]=0; } if(board[i][j]=='@') //상근이의 시작 위치 { q2.push({i,j}); dist2[i][j]=0; } } } //불에 대한 bfs while(!q1.empty()) { auto cur=q1.front();q1.pop(); for(int dir=0;dir<4;dir++) { int nx=cur.X+dx[dir]; int ny=cur.Y+dy[dir]; if(nx<0||nx>=h||ny<0||ny>=w) continue; if(dist1[nx][ny]>=0||board[nx][ny]=='#') continue; dist1[nx][ny]=dist1[cur.X][cur.Y]+1; q1.push({nx,ny}); } } //상근이에 대한 bfs while(!q2.empty()&&(!flag)) { auto cur=q2.front();q2.pop(); for(int dir=0;dir<4;dir++) { int nx=cur.X+dx[dir]; int ny=cur.Y+dy[dir]; if(nx<0||nx>=h||ny<0||ny>=w) //범위 벗어났다는것은 탈출 성공했다는 의미. { cout << dist2[cur.X][cur.Y]+1 << '\n'; flag=true; break; } if(dist2[nx][ny]>=0||board[nx][ny]=='#') continue; if(dist1[nx][ny]!=-1&&dist1[nx][ny]<=dist2[cur.X][cur.Y]+1) continue; dist2[nx][ny]=dist2[cur.X][cur.Y]+1; q2.push({nx,ny}); } } if(!flag) cout <<"IMPOSSIBLE" << '\n'; while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop(); } return 0; }
댓글을 작성하려면 로그인해야 합니다.
gerrard 4년 전 5
상근이에 대한 bfs를 돌린 후 상근이가 탈출했을 때 , flag를 설정해서 while문에서 더 도는걸 막아주세요.
+ 사용한 큐 초기화 해주셔야 다음 테스트 케이스에 영향을 받지 않는다고 합니다.
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long llu; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef pair<int, pii> piii; typedef pair<ll, ll> pll; typedef pair<ll, int> pli; typedef pair<int, ll> pil; typedef pair<string, int> psi; typedef pair<int, char> pic; #define X first #define Y second //if(nx<0||nx>=n||ny<0||ny>=m) continue; char board[1002][1002]; int dist1[1002][1002]; // 불의 전파속도 저장하는 배열 int dist2[1002][1002]; // 지훈이의 이동 저장하는 배열 int number; int w,h; // w는 열 h는 행의 수 int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); queue <pii> q1; queue <pii> q2; cin >> number; while(number--) { bool flag=false; cin >> w >> h; //h가 행. w가 열 for(int i=0;i<h;i++) { fill(dist1[i],dist1[i]+w,-1); fill(dist2[i],dist2[i]+w,-1); } for(int i=0;i<h;i++) for(int j=0;j<w;j++) cin >> board[i][j]; for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(board[i][j]=='*') //불이 난 위치 { q1.push({i,j}); dist1[i][j]=0; } if(board[i][j]=='@') //상근이의 시작 위치 { q2.push({i,j}); dist2[i][j]=0; } } } //불에 대한 bfs while(!q1.empty()) { auto cur=q1.front();q1.pop(); for(int dir=0;dir<4;dir++) { int nx=cur.X+dx[dir]; int ny=cur.Y+dy[dir]; if(nx<0||nx>=h||ny<0||ny>=w) continue; if(dist1[nx][ny]>=0||board[nx][ny]=='#') continue; dist1[nx][ny]=dist1[cur.X][cur.Y]+1; q1.push({nx,ny}); } } //상근이에 대한 bfs while(!q2.empty()&&(!flag)) { auto cur=q2.front();q2.pop(); for(int dir=0;dir<4;dir++) { int nx=cur.X+dx[dir]; int ny=cur.Y+dy[dir]; if(nx<0||nx>=h||ny<0||ny>=w) //범위 벗어났다는것은 탈출 성공했다는 의미. { cout << dist2[cur.X][cur.Y]+1 << '\n'; flag=true; break; } if(dist2[nx][ny]>=0||board[nx][ny]=='#') continue; if(dist1[nx][ny]!=-1&&dist1[nx][ny]<=dist2[cur.X][cur.Y]+1) continue; dist2[nx][ny]=dist2[cur.X][cur.Y]+1; q2.push({nx,ny}); } } if(!flag) cout <<"IMPOSSIBLE" << '\n'; while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop(); } return 0; }