글 읽기 - 5427번 어떤 반례가 있을까요?

eunpyokim 3년 전 0

게시판에 있는 반례에 대해 대부분 돌려보았을 때 문제없이 돌아가는 것 처럼 보였으나 또 다른 반례가 존재하는 것 같군요.

다른 반례도 이것저것 만들어서 돌려봤지만 잘 작동하는 것처럼 보입니다.

혹시 다른 반례 좀 알려주실 수 있을까요?

감사합니다.

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
int w, h;
int dist[2][1002][1002];

int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };

void bfs(vector<string> map, bool isfire, queue<pair<int, int>> q) {
	// 상근이 bfs: isfire = 0
	// 불     bfs: isfire = 1	
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= h || ny < 0 || ny >= w || map[nx][ny] == '#')
				continue;
			if (dist[isfire][nx][ny] != -1 && (dist[isfire][nx][ny] <= dist[isfire][x][y] + 1)) // 이 조건은 불이든 사람이든 적용가능 ? check 해봐
				continue;
			if (!isfire) { // 불로 bfs 하면 벽 빼고는 다 퍼지기 가능					
				if (map[nx][ny] != '.')
					continue;
				if (dist[1][nx][ny] != -1 && (dist[1][nx][ny] <= dist[0][x][y] + 1))
					continue;
			}
			q.push(make_pair(nx, ny));
			dist[isfire][nx][ny] = dist[isfire][x][y] + 1;
		}
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {		
		memset(dist, -1, sizeof(dist));		
		cin >> w >> h;
		vector<string> map(h + 2);
		queue<pair<int, int>> q;
		queue<pair<int, int>> fire_q;
		for (int i = 1; i < h+1; i++) {
			string tmp;
			cin >> tmp;
			tmp = '.' + tmp + '.';
			map[i] = tmp;
		}
		w += 2;
		h += 2;
		for (int i = 0; i < w; i++) {
			map[0] += '.';
			map[h - 1] += '.';
		}		
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (map[i][j] == '@') {
					q.push(make_pair(i, j));
					dist[0][i][j] = 0;
				}
				else if (map[i][j] == '*') {
					fire_q.push(make_pair(i, j));
					dist[1][i][j] = 0;
				}
			}
		}
		bfs(map, 1, fire_q);		
		bfs(map, 0, q);

		int ans = w*h;
		bool change_flag = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j += w - 1) {
				if (dist[0][i][j] != -1 && dist[0][i][j] < ans) {
					ans = dist[0][i][j];					
					change_flag = 1;
				}
			}
		}
		for (int j = 0; j < w; j++) {
			for (int i = 0; i < h; i+= h-1) {
				if (dist[0][i][j] != -1 && dist[0][i][j] < ans) {
					ans = dist[0][i][j];
					change_flag = 1;
				}
			}
		}		
		if (change_flag)
			cout << ans << '\n';
		else
			cout << "IMPOSSIBLE\n";
	}
}

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

문제

문제

출처

ICPC

5427번 어떤 반례가 있을까요?

eunpyokim 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말