#include #include typedef struct { char** F; //Current Field int v; //vertical size int h; //forizontal size int R[2]; //Red Position int B[2]; //Blue Pos int O[2]; //Hole Pos } space; void testshow(const space* const s) { printf("\n\n"); for(int i = 0; i < s->v; i++) { for(int j = 0; j < s->h; j++) printf("%c", s->F[i][j]); printf("\n"); } printf("Positions :\n"); printf("\tR : (%d, %d)\n", s->R[0], s->R[1]); printf("\tB : (%d, %d)\n", s->B[0], s->B[1]); printf("\tO : (%d, %d)\n", s->O[0], s->O[1]); return; } char dirfinder(space* const s); void move(space* s, const char direction); void free_memory(space* s, char**** visited, int** log); void dfs(space* s, int depth, char**** visited, int** log, char* min); int main() { char min = 11; int** log = (int**)calloc(10, sizeof(int*)); for(int i = 0; i < 10; i++) log[i] = (int*)calloc(5, sizeof(int)); space* s = (space*)calloc(1, sizeof(space)); scanf("%d%d", &s->v, &s->h); s->F = (char**)calloc(s->v, sizeof(char*)); for(int i = 0; i < s->v; i++) { getchar(); s->F[i] = (char*)calloc(s->h, sizeof(char)); for(int j = 0; j < s->h; j++) { scanf("%c", s->F[i] + j); if(s->F[i][j] == '#' || s->F[i][j] == '.') continue; else { if(s->F[i][j] == 'R') s->R[0] = i, s->R[1] = j; if(s->F[i][j] == 'B') s->B[0] = i, s->B[1] = j; if(s->F[i][j] == 'O') s->O[0] = i, s->O[1] = j; } } } // printf("\n\n\n"); //make a room in the console // 방문 상태 기록 배열 동적 할당 char**** visited = (char****)calloc(s->v + 1, sizeof(char***)); for (int i = 0; i <= s->v; i++) { visited[i] = (char***)calloc(s->h + 1, sizeof(char**)); for (int j = 0; j <= s->h; j++) { visited[i][j] = (char**)calloc(s->v + 1, sizeof(char*)); for (int k = 0; k <= s->v; k++) { visited[i][j][k] = (char*)calloc(s->h + 1, sizeof(char)); for(int l = 0; l <= s->h; l++) visited[i][j][k][l] = 11; } } } visited[s->R[0]][s->R[1]][s->B[0]][s->B[1]] = 0; dfs(s, 0, visited, log, &min); printf("%d\n", min == 11 ? -1 : min); free_memory(s, visited, log); return 0; } void dfs(space* s, int depth, char**** visited, int** log, char* min) { // printf("depth %d started\n", depth); // testshow(s); // printf("logs : \n"); // for(int i = 0; i < 10; i++) // { // for(int j = 0; j < 4; j++) printf("%d ", log[i][j]); // printf("\n"); // } if(depth >= 10) return; if(!s->R[0]) { if(s->B[0] && *min > depth) { *min = depth; // printf("Minimum Changed to %d\n", *min); } s->F[s->R[0]][s->R[1]] = s->F[s->B[0]][s->B[1]] = '.'; s->R[0] = log[depth][0], s->R[1] = log[depth][1]; s->B[0] = log[depth][2], s->B[1] = log[depth][3]; s->F[log[depth][0]][log[depth][1]] = 'R'; s->F[log[depth][2]][log[depth][3]] = 'B'; for(int i = 0; i < 5; i++) log[depth][i] = 0; return; } const char dir = dirfinder(s); // printf("\n\ndepth : %d, dir candidate : %4b\n\n", depth, dir); if(dir&0b0001) { // printf("up in depth %d\n", depth); log[depth][0] = s->R[0]; log[depth][1] = s->R[1]; log[depth][2] = s->B[0]; log[depth][3] = s->B[1]; log[depth][4] = depth; move(s, 0b0001); if(visited[s->R[0]][s->R[1]][s->B[0]][s->B[1]] <= depth + 1) { s->F[s->R[0]][s->R[1]] = s->F[s->B[0]][s->B[1]] = '.'; s->R[0] = log[depth][0], s->R[1] = log[depth][1]; s->B[0] = log[depth][2], s->B[1] = log[depth][3]; s->F[log[depth][0]][log[depth][1]] = 'R'; s->F[log[depth][2]][log[depth][3]] = 'B'; for(int i = 0; i < 5; i++) log[depth][i] = 0; } else { visited[s->R[0]][s->R[1]][s->B[0]][s->B[1]] = depth + 1; dfs(s, depth + 1, visited, log, min); } } if(dir&0b0010) { // printf("down in depth %d\n", depth); log[depth][0] = s->R[0]; log[depth][1] = s->R[1]; log[depth][2] = s->B[0]; log[depth][3] = s->B[1]; log[depth][4] = depth; move(s, 0b0010); if(visited[s->R[0]][s->R[1]][s->B[0]][s->B[1]] <= depth + 1) { s->F[s->R[0]][s->R[1]] = s->F[s->B[0]][s->B[1]] = '.'; s->R[0] = log[depth][0], s->R[1] = log[depth][1]; s->B[0] = log[depth][2], s->B[1] = log[depth][3]; s->F[log[depth][0]][log[depth][1]] = 'R'; s->F[log[depth][2]][log[depth][3]] = 'B'; for(int i = 0; i < 5; i++) log[depth][i] = 0; } else { visited[s->R[0]][s->R[1]][s->B[0]][s->B[1]] = depth + 1; dfs(s, depth + 1, visited, log, min); } } if(dir&0b0100) { // printf("left in depth %d\n", depth); log[depth][0] = s->R[0]; log[depth][1] = s->R[1]; log[depth][2] = s->B[0]; log[depth][3] = s->B[1]; log[depth][4] = depth; move(s, 0b0100); if(visited[s->R[0]][s->R[1]][s->B[0]][s->B[1]] <= depth + 1) { s->F[s->R[0]][s->R[1]] = s->F[s->B[0]][s->B[1]] = '.'; s->R[0] = log[depth][0], s->R[1] = log[depth][1]; s->B[0] = log[depth][2], s->B[1] = log[depth][3]; s->F[log[depth][0]][log[depth][1]] = 'R'; s->F[log[depth][2]][log[depth][3]] = 'B'; for(int i = 0; i < 5; i++) log[depth][i] = 0; } else { visited[s->R[0]][s->R[1]][s->B[0]][s->B[1]] = depth + 1; dfs(s, depth + 1, visited, log, min); } } if(dir&0b1000) { // printf("right in depth %d\n", depth); log[depth][0] = s->R[0]; log[depth][1] = s->R[1]; log[depth][2] = s->B[0]; log[depth][3] = s->B[1]; log[depth][4] = depth; move(s, 0b1000); if(visited[s->R[0]][s->R[1]][s->B[0]][s->B[1]] <= depth + 1) { s->F[s->R[0]][s->R[1]] = s->F[s->B[0]][s->B[1]] = '.'; s->R[0] = log[depth][0], s->R[1] = log[depth][1]; s->B[0] = log[depth][2], s->B[1] = log[depth][3]; s->F[log[depth][0]][log[depth][1]] = 'R'; s->F[log[depth][2]][log[depth][3]] = 'B'; for(int i = 0; i < 5; i++) log[depth][i] = 0; } else { visited[s->R[0]][s->R[1]][s->B[0]][s->B[1]] = depth + 1; dfs(s, depth + 1, visited, log, min); } } // printf("depth %d exit\n\n", depth); if(depth) { s->F[s->R[0]][s->R[1]] = s->F[s->B[0]][s->B[1]] = '.'; depth--; s->R[0] = log[depth][0], s->R[1] = log[depth][1]; s->B[0] = log[depth][2], s->B[1] = log[depth][3]; s->F[log[depth][0]][log[depth][1]] = 'R'; s->F[log[depth][2]][log[depth][3]] = 'B'; for(int i = 0; i < 5; i++) log[depth][i] = 0; } // testshow(s); return; } char dirfinder(space* const s) { char ans = 0; if(!(s->R[0] * s->R[1] * s->B[0] * s->B[1])) return ans; if(s->F[s->R[0] - 1][s->R[1]] == '.' || s->F[s->R[0] - 1][s->R[1]] == 'O') ans |= 0b0001; //u if(s->F[s->B[0] - 1][s->B[1]] == '.' || s->F[s->B[0] - 1][s->B[1]] == 'O') ans |= 0b0001; if(s->F[s->R[0] + 1][s->R[1]] == '.' || s->F[s->R[0] + 1][s->R[1]] == 'O') ans |= 0b0010; //d if(s->F[s->B[0] + 1][s->B[1]] == '.' || s->F[s->B[0] + 1][s->B[1]] == 'O') ans |= 0b0010; if(s->F[s->R[0]][s->R[1] - 1] == '.' || s->F[s->R[0]][s->R[1] - 1] == 'O') ans |= 0b0100; //l if(s->F[s->B[0]][s->B[1] - 1] == '.' || s->F[s->B[0]][s->B[1] - 1] == 'O') ans |= 0b0100; if(s->F[s->R[0]][s->R[1] + 1] == '.' || s->F[s->R[0]][s->R[1] + 1] == 'O') ans |= 0b1000; //r if(s->F[s->B[0]][s->B[1] + 1] == '.' || s->F[s->B[0]][s->B[1] + 1] == 'O') ans |= 0b1000; return ans; } // Find Available Direction void move(space* s, const char direction) { const int u[2] = {-1, 0}, d[2] = {1, 0}, l[2] = {0, -1}, r[2] = {0, 1}; const int* dir = NULL; if(direction&0b0001) dir = u; else if(direction&0b0010) dir = d; else if(direction&0b0100) dir = l; else if(direction&0b1000) dir = r; else { // printf("\ndirection error\n"); return; } while(s->F[s->R[0] + dir[0]][s->R[1] + dir[1]] == '.' || s->F[s->R[0] + dir[0]][s->R[1] + dir[1]] == 'O') { s->F[s->R[0]][s->R[1]] = '.'; s->R[0] += dir[0]; s->R[1] += dir[1]; if(s->F[s->R[0]][s->R[1]] == '.') s->F[s->R[0]][s->R[1]] = 'R'; else { s->R[0] = s->R[1] = 0; break; } } while(s->F[s->B[0] + dir[0]][s->B[1] + dir[1]] == '.' || s->F[s->B[0] + dir[0]][s->B[1] + dir[1]] == 'O') { s->F[s->B[0]][s->B[1]] = '.'; s->B[0] += dir[0]; s->B[1] += dir[1]; if(s->F[s->B[0]][s->B[1]] == '.') s->F[s->B[0]][s->B[1]] = 'B'; else { s->B[0] = s->B[1] = 0; break; } } if(s->R[0] + s->R[1]) while(s->F[s->R[0] + dir[0]][s->R[1] + dir[1]] == '.' || s->F[s->R[0] + dir[0]][s->R[1] + dir[1]] == 'O') { s->F[s->R[0]][s->R[1]] = '.'; s->R[0] += dir[0]; s->R[1] += dir[1]; if(s->F[s->R[0]][s->R[1]] == '.') s->F[s->R[0]][s->R[1]] = 'R'; else { s->R[0] = s->R[1] = 0; break; } } // testshow(s); return; } // 메모리 해제 코드 void free_memory(space* s, char**** visited, int** log) { // 1. visited 배열 해제 if (visited != NULL) { for (int i = 0; i <= s->v; i++) { for (int j = 0; j <= s->h; j++) { for (int k = 0; k <= s->v; k++) { free(visited[i][j][k]); // 4차원 가장 안쪽 배열 해제 } free(visited[i][j]); // 3차원 배열 해제 } free(visited[i]); // 2차원 배열 해제 } free(visited); // 1차원 배열 해제 } // 2. space 구조체 내부 배열 해제 if (s != NULL) { for (int i = 0; i < s->v; i++) { free(s->F[i]); // 현재 필드 해제 } free(s->F); // 2차원 배열 F 해제 // space 구조체 자체 해제 free(s); } if (log) { for(int i = 0; i < 10; i++) free(log[i]); free(log); } return; }

제출 #50702

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: