글 읽기 - 반례 부탁드리겠습니다..

rladudrb1200 1년 전 0

5427번 불 문제입니다.

기본적으로 불을 먼저 이동하면서 갈수있는곳에 * 표시로 변경해줬고,

상근이가 이동하도록 하였습니다.

테스트케이스와 질문게시판 테스트케이스를 다 돌렸지만 잘 돌아가는데.. 왜 틀리다고 뜨는지 모르겠습니다.

부탁드리겠습니다.

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int w, h;
char maps[1005][1005];
bool visited[1005][1005];
queue<pair<pair<int,int>,int> > person_q;
queue<pair<int,int> > fire_q;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

void init(){
	cin >> w >> h;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			scanf("%1s",&maps[i][j]);
			if(maps[i][j] == '@'){
				person_q.push(make_pair(make_pair(i,j), 0));
			}
			if(maps[i][j] == '*'){
				fire_q.push(make_pair(i,j));
			}
		}
	}
}

void print(){
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			cout << maps[i][j];
		}
		cout << endl;
	}
	cout << endl;
}

int bfs(){
	//사람이동이존재할동안반복 
	while(!person_q.empty()){
		
		//불부터이동
		int fireSize = fire_q.size();
		for(int i=0; i<fireSize; i++){
			int x = fire_q.front().first;
			int y = fire_q.front().second;
			fire_q.pop();
			
			for(int j=0; j<4; j++){
				int nx = x + dx[j];
				int ny = y + dy[j];
				
				if(nx >= 0 && ny >= 0 && nx < h && ny < w){
					if(maps[nx][ny] != '#' && maps[nx][ny] !='*'){
						maps[nx][ny] = '*';
						fire_q.push(make_pair(nx, ny));
					}
				}
			}	
		}
		
		//print();
		//상근이이동
		int personSize = person_q.size();
		for(int i=0; i<personSize; i++){
			int px = person_q.front().first.first;
			int py = person_q.front().first.second;
			int cnt = person_q.front().second;
			visited[px][py] = true;
			person_q.pop();
			
			if(px == 0 || py == 0 || px == h-1 || py == w-1){
				//cout << "상근이 탈출 : " << px << "," << py << endl;
				return cnt + 1;
			}
			
			for(int i=0; i<4; i++){
				int npx = px + dx[i];
				int npy = py + dy[i];
				 
				if(npx >= 0 && npy >= 0 && npx < h && npy < w){
					if(maps[npx][npy] == '.' && visited[npx][npy] == false){
						//cout << "상근이 이동 : " << npx << "," << npy << endl;
						visited[npx][npy] = true;
						person_q.push(make_pair(make_pair(npx,npy), cnt+1));
					}
				}
			}	
		} 

	}
	
	return -1;
}

int main(){
	
	int t;
	cin >> t;
	while(t--){
		memset(visited, false, sizeof(visited));
		while(!fire_q.empty()){
			fire_q.pop();
		}
		
		init();
		int r = bfs();
		if(r == -1){
			cout << "IMPOSSIBLE" << endl;
		}else{
			cout << r << endl;
		}
		
	}
	
	return 0;
}

tkdgus115 1년 전 0

1
7 6
###.###
###.###
#.....#
#.....#
#..@..#
#######

입력예제 부분을 바꿨어요

불이 하나도 없을때 생각해보세요

rladudrb1200 1년 전 0

tkdgus 님,

근데 불이 하나도 없어도 상근이는 탈출 해야하는거 아닌가요?

보여주신 예제 돌리면 5라는 값이 나오는데,

어쨌든 출구는 있으니 탈출 시켜야 하는거 아닌가요?

tkdgus115 1년 전 0

제가 남긴 예제는 5가 답이 맞아요

5가 나오면 맞고요 님코드는 불돌리는 코드하고 사람 돌리는 코드 같이있어서 로직이 복잡하네요

그리고 test마다 맵하고 비지트 초기화해주세요

지금 님 코드 보면 불 돌리고나서 사람 돌리시는데

그것 보다 불만 먼저 다돌리시고

사람 돌리는 함수 따로 만들어서 해보세요

그리고 불이 1개가 아니라 3개일경우도 생각하시고요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례 부탁드리겠습니다..

rladudrb1200 1년 전 0

tkdgus115 1년 전 0

rladudrb1200 1년 전 0

tkdgus115 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말