5427 불

불

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	10778	2359	1413	20.853%

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w와 h가 주어진다. (1 ≤ w,h ≤ 1000)

다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

각 지도에 @의 개수는 하나이다.

출력

각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

==

불을 1단계 옮겨붙게하고, 사람을 1단계옮겨가면서

사람이 빌딩 가장자리에 도착했을때 끝내면된다.

이게뭐라고 시간을 너무 오래썼다.

좀더 빠르게 문제를 푸는 연습을 해야겠다.

#include <bits/stdc++.h>

using namespace std;

int x_direction[4] = {-1,1,0,0};

int y_direction[4] = {0,0,-1,1};

struct Pos{

int x;

int y;

};

int w,h;

char building[1001][1001];

bool fired[1001][1001];

bool visited[1001][1001];

queue<Pos> fire_que;

queue<Pos> person_que;

int bfs();

int main(){

freopen("input.txt","r",stdin);

ios::sync_with_stdio(false);

cin.tie(0);

int T;

cin>>T;

char temp;

for(int t=0; t<T; ++t){

memset(building, '.', sizeof(building));

memset(fired, false, sizeof(fired));

memset(visited, false, sizeof(visited));

fire_que = queue<Pos>();

person_que = queue<Pos>();

cin>>w>>h;

for(int i=0; i<h; ++i){

for(int j=0; j<w; ++j){

cin>>temp;

switch(temp){

case '@':

person_que.push({i,j});

visited[i][j] = true;

break;

case '*':

fire_que.push({i,j});

fired[i][j] = true;

break;

default:

break;

}

building[i][j] = temp;

}

}

// for(int a=0; a<h; ++a){

// for(int b=0; b<w; ++b){

// cout<<building[a][b]<<" ";

// }

// cout<<"\n";

// }

int answer = bfs();

if(answer == -1){

cout<<"IMPOSSIBLE\n";

} else{

cout<<answer<<"\n";

}

} //test case end

return 0;

}

int bfs(){

Pos fire_pos;

Pos person_pos;

int fire_step_width = fire_que.size();

int person_step_width = person_que.size();

int tmp=1;

while(!fire_que.empty() || !person_que.empty()){

fire_step_width = fire_que.size();

for(int s=0; s<fire_step_width; ++s){

fire_pos = fire_que.front();

fire_que.pop();

for(int i=0; i<4; ++i){ // move fire

if(

(fire_pos.x+x_direction[i]>=0 && fire_pos.x+x_direction[i]<h) &&

(fire_pos.y+y_direction[i]>=0 && fire_pos.y+y_direction[i]<w) &&

(!fired[fire_pos.x+x_direction[i]][fire_pos.y+y_direction[i]]) && // check !='*'

(building[fire_pos.x+x_direction[i]][fire_pos.y+y_direction[i]] != '#') //no wall

){

fire_que.push({fire_pos.x+x_direction[i],fire_pos.y+y_direction[i]});

fired[fire_pos.x+x_direction[i]][fire_pos.y+y_direction[i]] = true;

}

}

}

person_step_width = person_que.size();

for(int s=0; s<person_step_width; ++s){

person_pos = person_que.front();

person_que.pop();

for(int i=0; i<4; ++i){ // move person

if(

(person_pos.x+x_direction[i]>=0 && person_pos.x+x_direction[i]<h) &&

(person_pos.y+y_direction[i]>=0 && person_pos.y+y_direction[i]<w) &&

(!visited[person_pos.x+x_direction[i]][person_pos.y+y_direction[i]]) &&

(building[person_pos.x+x_direction[i]][person_pos.y+y_direction[i]] != '#') && // no wall

(fired[person_pos.x+x_direction[i]][person_pos.y+y_direction[i]] == false) // no fire

){

person_que.push({person_pos.x+x_direction[i],person_pos.y+y_direction[i]});

visited[person_pos.x+x_direction[i]][person_pos.y+y_direction[i]] = true;

}

else if(

!((person_pos.x+x_direction[i]>=0 && person_pos.x+x_direction[i]<h) &&

(person_pos.y+y_direction[i]>=0 && person_pos.y+y_direction[i]<w) )

) {

return tmp;

}

}

}

tmp++;

}

return -1;

}