글 읽기 - 반례 질문드립니다.

arsgsg 3년 전 1

bfs로 불이 먼저 이동한 후 상근이가 이동하는 방식으로 풀었습니다.

그런데 예제 케이스와 질문검색에 있는 케이스를 모두 돌려봐도 답으로 나오지만 틀렸습니다가 뜹니다.

/*
5427 불 (https://www.acmicpc.net/problem/5427)
*/
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX_LEN 1003
char field[MAX_LEN][MAX_LEN] = { {0, 0} };
int person[MAX_LEN][MAX_LEN] = { {0, 0} };
int width, height;
queue<pair<int, int> >fq;
queue<pair<int, int> >pq;
int dirRow[] = { 1, -1, 0 , 0 };
int dirCol[] = { 0, 0, 1, -1 };
int Solution()
{
	//bfs로 불이 먼저 이동한 후 상근이가 이동합니다
	int nr, nc, cr, cc;
	while (!pq.empty()) 
	{
		//불의 이동
		if (!fq.empty()) {
			cr = fq.front().first;
			cc = fq.front().second;
			for (int i = 0; i < 4; i++) {
				nr = cr + dirRow[i];
				nc = cc + dirCol[i];
				if (nc < 0 || nr < 0 || nc >= width || nr >= height) {
					continue;
				}
				//불이 이동칸이 빈 칸이므로 옮겨붙는 경우
				if (field[nr][nc] == '.') {
					field[nr][nc] = '*';
					fq.push(make_pair(nr, nc));
				}
			}
			fq.pop();
		}
		//상근이의 이동
		cr = pq.front().first;
		cc = pq.front().second;
		//상근이가 가장자리에 도달하면 탈출에 성공한 것으로 봅니다.
		if (cr == 0 || cc == 0 || cr == height - 1 || cc == width - 1) {
			printf("%d\n", person[cr][cc]);
			return person[cr][cc];
		}
		for (int i = 0; i < 4; i++) {
			nr = cr + dirRow[i];
			nc = cc + dirCol[i];
			//상근이가 이동한 경로는 다시 큐에 넣지 않고, 빈 칸일 때만 넣습니다.
			if (field[nr][nc] == '.' && person[nr][nc] == false) {
				person[nr][nc] = person[cr][cc] + 1;
				pq.push(make_pair(nr, nc));
			}
		}
		pq.pop();
	}
	printf("IMPOSSIBLE\n");
	return 0;
}

int main()
{
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> width >> height;
		for (int j = 0; j < height; j++) {
			for (int k = 0; k < width; k++) {
				cin >> field[j][k];
				if (field[j][k] == '*') {
					fq.push(make_pair(j, k));
				}
				if (field[j][k] == '@') {
					person[j][k] = true;
					pq.push(make_pair(j, k));
				}
			}
		}
		Solution();
		fill(&person[0][0], &person[MAX_LEN][MAX_LEN], 0);
		while (!fq.empty()) fq.pop();
		while (!pq.empty()) pq.pop();
	}
	return 0;
}

tony9402 3년 전 1

반례 드립니다.

1
7 7
#.#####
#.....#
#####.#
#....*#
####.##
#@....#
#####.#

답 : IMPOSSIBLE

OUTPUT : 6

arsgsg 3년 전 1

감사합니다 해결했습니다.

bfs할 때 큐에 넣은 항들을 하나씩만 방문한게 문제였네요

큐에 넣은 항들의 개수를 저장해서 돌리도록 수정했습니다 ㅎㅎ

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

문제

문제

출처

ICPC

반례 질문드립니다.

arsgsg 3년 전 1

tony9402 3년 전 1

arsgsg 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말