글 읽기 - 반례가 뭐가 있을까요?

qwerteh 3년 전 0

문제점을 못 찾았습니다ㅠㅠ

#include<iostream>
#include<utility>
#include<queue>
#include<cstring>

using namespace std;

int t, w, h;
char board[1002][1002];
int fire[1002][1002];
int dist[1002][1002];

#define X first
#define Y second

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
queue<pair<int, int>> fire_Q;
queue<pair<int, int>> s_Q;
//불 bfs
void fire_bfs() {
	while (!fire_Q.empty()) {
		auto cur = fire_Q.front(); fire_Q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
			if (board[nx][ny] == '#' || fire[nx][ny] != -1) continue;
			fire[nx][ny] = fire[cur.X][cur.Y] + 1;
			fire_Q.push({ nx,ny });
		}
	}
}

//상근이 bfs
int num = 0;

bool s_bfs() {
	while (!s_Q.empty()) {
		auto cur = s_Q.front(); s_Q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
				num = dist[cur.X][cur.Y]+1; return 1;
			}
			if (dist[nx][ny] != -1 || board[nx][ny] != '.') continue;
			if (fire[nx][ny] != -1 && fire[nx][ny] <= dist[cur.X][cur.Y] + 1) continue;
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
			s_Q.push({ nx,ny });
		}
	}
	return 0;
}

int main() {
	cin >> t;
	while (t--) {
		//배열 초기화
		memset(dist, -1, sizeof(dist));
		memset(fire, -1, sizeof(fire));
		memset(board, 0, sizeof(board));
		cin >> w >> h;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> board[i][j];
				if (board[i][j] == '*') {
					fire_Q.push({ i,j });
					fire[i][j] = 0;
				}
				if (board[i][j] == '@') {
					s_Q.push({ i,j });
					dist[i][j] = 0;
				}
			}
		}
		

		
		fire_bfs();
		bool ck = s_bfs();
		if (ck == 1) {
			cout << num;
		}
		else {
			cout << "IMPOSSIBLE";
		}
		
		cout << '\n';

	}
}

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

문제

문제

출처

ICPC

반례가 뭐가 있을까요?

qwerteh 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말