#define _CRT_SECURE_NO_WARNINGS #include #include typedef struct Q { int x; int y; } Q; int dx[4] = { 1, 0, -1, 0 }; int dy[4] = { 0, 1, 0, -1 }; void push(Q* queue, int* tail, int i, int j); void pop(int* head); int main() { int r, c; scanf("%d %d", &r, &c); // 필요한 배열 할당 char** s = (char**)malloc(r * sizeof(char*)); for (int i = 0; i < r; i++) { s[i] = (char*)malloc((c + 1) * sizeof(char)); } int** fire = (int**)malloc(r * sizeof(int*)); int** jihun = (int**)malloc(r * sizeof(int*)); for (int i = 0; i < r; i++) { fire[i] = (int*)malloc(c * sizeof(int)); jihun[i] = (int*)malloc(c * sizeof(int)); } Q* queue = (Q*)calloc(r * c, sizeof(Q)); for (int i = 0; i < r; i++) { scanf("%s", s[i]); } // 불의 시간 구하기 위한 BFS int head = 0, tail = 0; for (int i = 0; i < r; i++) { for (int k = 0; k < c; k++) { if (s[i][k] == '*') { push(queue, &tail, i, k); fire[i][k] = 0; } else { fire[i][k] = -1; } } } while (head != tail) { int x = queue[head].x; int y = queue[head].y; pop(&head); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue; if (fire[nx][ny] != -1 || s[nx][ny] != '.') continue; fire[nx][ny] = fire[x][y] + 1; push(queue, &tail, nx, ny); } } // 지훈이의 시간 구하기 위한 BFS head = 0; tail = 0; for (int i = 0; i < r; i++) { for (int k = 0; k < c; k++) { if (s[i][k] == '@') { push(queue, &tail, i, k); jihun[i][k] = 0; if (i == 0 || k == 0 || i == r - 1 || k == c - 1) { printf("1"); goto end; } } else { jihun[i][k] = -1; } } } while (head != tail) { int x = queue[head].x; int y = queue[head].y; pop(&head); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue; if (jihun[nx][ny] != -1 || s[nx][ny] != '.') continue; if (fire[nx][ny] != -1 && fire[nx][ny] <= jihun[x][y] + 1) continue; jihun[nx][ny] = jihun[x][y] + 1; push(queue, &tail, nx, ny); if (nx == 0 || ny == 0 || nx == r - 1 || ny == c - 1) { printf("%d\n", jihun[nx][ny] + 1); goto end; } } } printf("IMPOSSIBLE\n"); end: for (int i = 0; i < r; i++) { free(s[i]); free(fire[i]); free(jihun[i]); } free(fire); free(jihun); free(s); free(queue); return 0; } void push(Q* queue, int* tail, int i, int j) { queue[*tail].x = i; queue[*tail].y = j; (*tail)++; } void pop(int* head) { (*head)++; }

제출 #14369

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: