글 읽기 - 반례점 찾아주세요...

mw9911 5년 전 0

어느 부분이 틀린지 모르겠어요..

#include<stdio.h>
#include<string.h>
int M,N,X, Y, e, s,eF,sF,et,eFt;
int Mchk[1010][1010];
char map[1010][1010];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
typedef struct kim {
	int x;
	int y;
	int cnt;
}mw;
mw q[1000100];
mw qF[1000100];
mw pop() {
	return q[s++];
}
void push(mw a) {
	Mchk[a.y][a.x] = 1;
	q[e++] = a;
}
int main() {
	int t;
	int ch = 0;
	scanf("%d", &t);
	char c;
	for (int fin = 0; fin < t; fin++) {
		ch = 0;
		s = 0; e = 0; eF = 0; sF = 0;
		memset(Mchk, 0, sizeof(Mchk));
		memset(map, 0, sizeof(map));
		memset(q, 0, sizeof(q));
		memset(qF, 0, sizeof(qF));
		scanf("%d %d", &M, &N);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= M; j++) {
				scanf("%c", &c);
				map[i][j] = c;
				if (c == '*') {
					qF[eF++] = { j,i,-1 };
				}
				if (c == '@') {
					map[i][j] = '.';
					q[e++] = { j,i,0 };
					Mchk[i][j] = 1;
				}
			}
		}

		for (int fi = 0; fi < N*M; fi++) {
			
			et = e;
			while (s != et) {
				if(map[q[s].y][q[s].x]=='.')
				for (int i = 0; i < 4; i++) {
					X = q[s].x + dx[i];
					Y = q[s].y + dy[i];
					if (X > M || Y >= N || Y < 0 || X <= 0) {
						break;
						
					}
					if (X > 0 && X <= M&&Y >= 0 && Y < N) {
						if (Mchk[Y][X] == 0 && map[Y][X] == '.') {
							q[e++] = { X,Y,q[s].cnt + 1 };
							Mchk[Y][X] = 1;
						}
					}
				}

				if (X > M || Y >= N || Y < 0 || X <= 0) {
					ch = 1;
					break;

				}
				s++;
			}
			if (ch==1) {
				break;

			}
			eFt = eF;
			while (sF != eFt) {
				for (int i = 0; i < 4; i++) {
					X = qF[sF].x + dx[i];
					Y = qF[sF].y + dy[i];
					if (X > 0 && X <= M && Y >= 0 && Y < N) {
						if (map[Y][X] == '.') {
							map[Y][X] = '*';
							qF[eF++] = { X,Y,-1 };
						}
					}
				}

				sF++;
			}

		}
		if (ch==1) {
			printf("%d\n", q[s].cnt + 1);

		}
		else {
			printf("IMPOSSIBLE\n");
		}
	}
}

Glitterlance 5년 전 0

이거 BFS로 하신 거 맞죠?

반례까지는 모르겠지만 팁을 드리자면, 먼저 불이 진행되는 걸 BFS로 구한 다음에 탈출 시간을 구하는 방법이 더 간단할 겁니다.

그리고 이 링크에 있는 글을 참조해주세요.

https://www.acmicpc.net/board/...

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

문제

문제

출처

ICPC

반례점 찾아주세요...

mw9911 5년 전 0

Glitterlance 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말