#include #include #include #pragma warning(disable:4996) int** visit; int tri, n, m, ptr; //BFS로 방문한 좌표를 저장하는 배열 int* ax, * ay; int direc_x[4] = { 1, 0, -1, 0 }; int direc_y[4] = { 0, 1, 0, -1 }; //BFS를 위한 큐 typedef struct { int* y; int* x; int num; int rear; int front; int max; } Queue; //큐 초기화 void Ini(Queue* q) { q->max = n * m; q->y = (int*)calloc(n * m, sizeof(int)); q->x = (int*)calloc(n * m, sizeof(int)); q->rear = q->front = q->num = 0; } void Enque(Queue* q, int x, int y) { q->x[q->rear] = x; q->y[q->rear] = y; q->rear++; q->num++; } int De_x(Queue* q) { int temp = q->x[q->front]; return temp; } int De_y(Queue* q) { int temp = q->y[q->front]; return temp; } //좌표 디큐 void Deque(Queue* q, int* x, int* y) { *x = De_x(q); *y = De_y(q); q->front++; q->num--; } int Empty(Queue* q) { return (q->num != 0); } void Termi(Queue* q) { free(q->x); free(q->y); q->num = q->max = q->front = q->rear = 0; } void BFS(int x, int y) { int px, py; int start = ptr; px = x; py = y; //큐에 방문한 좌표를 넣으면서 tri = 0; Queue q; Ini(&q); Enque(&q, px, py); visit[py][px] = 2; //ax, ay 배열에도 방문한 배열의 좌표를 추가 ax[ptr] = x; ay[ptr++] = y; if (ay[ptr - 1] == n - 1) tri = 1; //방문한 좌표는 '2'로 수정, 바닥이 있을 경우 tri를 1로 변경해둠 while (Empty(&q)) { Deque(&q, &px, &py); for (int i = 0; i < 4; i++) { if (px + direc_x[i] >= 0 && px + direc_x[i] < m && py + direc_y[i] >= 0 && py + direc_y[i] < n) { if (visit[py + direc_y[i]][px + direc_x[i]] == 1) { visit[py + direc_y[i]][px + direc_x[i]] = 2; Enque(&q, px + direc_x[i], py + direc_y[i]); ax[ptr] = px + direc_x[i]; ay[ptr++] = py + direc_y[i]; if (ay[ptr - 1] == n - 1) tri = 1; } } } } //바닥에 닿지 않았을 경우 떨어져야 한다. //ax, ay에 저장해둔 좌표를 꺼내서 떨어지게 만들어줌 //이 때 값은 3으로 변경 //땅에 닿을 경우 tri를 1로 변경 while (1) { if (tri == 1) break; else { int i; for (i = start; i < ptr; i++) { visit[ay[i]][ax[i]] = -1; visit[ay[i] + 1][ax[i]] = 3; ay[i]++; if (ay[i] + 1 == n) tri = 1; else if (visit[ay[i] + 1][ax[i]] == 1 || visit[ay[i] + 1][ax[i]] == 2) tri = 1; } } } for (int i = start; i < ptr; i++) { visit[ay[i]][ax[i]] = 2; } Termi(&q); } int main() { int i, j, cnt, height; char temp; scanf("%d%d", &n, &m); getchar(); visit = (int**)calloc(n, sizeof(int*)); for (i = 0; i < n; i++) { visit[i] = (int*)calloc(m, sizeof(int)); } for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { scanf("%c", &temp); if (temp == 'x') visit[i][j] = 1; else visit[i][j] = -1; } getchar(); } scanf("%d", &cnt); ax = (int*)calloc(n * m * cnt, sizeof(int)); ay = (int*)calloc(n * m * cnt, sizeof(int)); for (i = 0; i < cnt; i++) { scanf("%d", &height); if (i % 2 == 0) { j = 0; while (1) { if (j == m) break; if (visit[n - height][j] == 1) { visit[n - height][j] = 0; break; } else j++; } } else if (i % 2 == 1) { j = m - 1; while (1) { if (j == -1) break; if (visit[n - height][j] == 1) { visit[n - height][j] = 0; break; } else j--; } } ptr = 0; for (int a = n - 1; a >= 0; a--) { for (int b = 0; b < m; b++) { if (visit[a][b] == 1) { BFS(b, a); } } } if (tri == 1) { int i; for (i = 0; i < ptr; i++) { visit[ay[i]][ax[i]] = 1; } } } for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { if (visit[i][j] == 1) printf("x"); else printf("."); } if (i != n - 1) printf("\n"); } return 0; }

제출 #142051

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: