// 일단 중복된 숫자는 걸러냄. #include #include void printBoard(int map[10][10]); int stepUpdate(int direction); int fullUpdate(int direction); int isChanged(int prevMap[10][10], int presMap[10][10]); void copyBoard(int targetBoard[10][10], int subjBoard[10][10]); int map[10][10] = {0}; // board || 1: 벽 / 2: 빈 공간 / 3: 빨간 공 / 4: 파란 공 / 5: 도착점 int redBall_x = 0, redBall_y = 0; // 행-렬 -> x-y Plane int blueBall_x = 0, blueBall_y = 0; // 첫번째 칸 -> (0,0) int main(void) { // Input int width, height; // width는 가로, height는 세로 scanf("%d %d", &height, &width); getchar(); for (int i = 0; i < height; i++) { for (int ii = 0; ii < width;) { char term = getchar(); if (term == '\n') continue; if (term == '#') { map[i][ii] = 1; } else if (term == '.') { map[i][ii] = 2; } else if (term == 'R') { map[i][ii] = 3; redBall_x = i; redBall_y = ii; } else if (term == 'B') { map[i][ii] = 4; blueBall_x = i; blueBall_y = ii; } else { map[i][ii] = 5; } ii++; } } int originBoard[10][10] = {0}; copyBoard(originBoard, map); int redBall_origin_x = redBall_x; int redBall_origin_y = redBall_y; int blueBall_origin_x = blueBall_x; int blueBall_origin_y = blueBall_y; // Process // 4**10 == 1048576 int minimum = 11; // minimum은 커야 10 이하 for (int i = 0; i < 1048576; i++) { copyBoard(map, originBoard); redBall_x = redBall_origin_x; redBall_y = redBall_origin_y; blueBall_x = blueBall_origin_x; blueBall_y = blueBall_origin_y; int actionArray[10] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}; for (int ii = 0; ii < 10; ii++) { actionArray[ii] = (i / (int)pow(4, ii)) % 4; } int isContinue = 0; for (int ii = 0; ii < 9; ii++) { if (actionArray[ii] == actionArray[ii + 1]) { isContinue = 1; break; } } if (isContinue == 1) { continue; } int cnt = 0; for (int ii = 0; ii < 10; ii++) { int caseResult = 0; cnt++; caseResult = fullUpdate(actionArray[ii]); if (caseResult >= 1) { if (cnt < minimum) { minimum = cnt; } break; } else if (caseResult <= -1) { break; } } } // Output if (minimum == 11) { printf("-1"); } else { printf("%d", minimum); } } void printBoard(int map[10][10]) { for (int i = 0; i < 10; i++) { for (int ii = 0; ii < 10; ii++) { printf("%d", map[i][ii]); } puts(""); } } void copyBoard(int targetBoard[10][10], int subjBoard[10][10]) { for (int i = 0; i < 10; i++) { for (int ii = 0; ii < 10; ii++) { targetBoard[i][ii] = subjBoard[i][ii]; } } } int stepUpdate(int direction) { // direction || 0: Right / 1: Down / 2: Left / 3: Up int returnValue = 0; if (direction == 0) { // Red 이동 if (map[redBall_x][redBall_y + 1] == 5) { returnValue = 1; map[redBall_x][redBall_y] = 2; } else if (map[redBall_x][redBall_y + 1] == 2) { map[redBall_x][redBall_y++] = 2; map[redBall_x][redBall_y] = 3; } // Blue 이동 if (map[blueBall_x][blueBall_y + 1] == 5) { returnValue = -1; map[redBall_x][redBall_y] = 2; } else if (map[blueBall_x][blueBall_y + 1] == 2) { map[blueBall_x][blueBall_y++] = 2; map[blueBall_x][blueBall_y] = 4; } return returnValue; } if (direction == 1) { // Red 이동 if (map[redBall_x + 1][redBall_y] == 5) { returnValue = 1; map[redBall_x][redBall_y] = 2; } else if (map[redBall_x + 1][redBall_y] == 2) { map[redBall_x++][redBall_y] = 2; map[redBall_x][redBall_y] = 3; } // Blue 이동 if (map[blueBall_x + 1][blueBall_y] == 5) { returnValue = -1; map[redBall_x][redBall_y] = 2; } else if (map[blueBall_x + 1][blueBall_y] == 2) { map[blueBall_x++][blueBall_y] = 2; map[blueBall_x][blueBall_y] = 4; } return returnValue; } if (direction == 2) { // Red 이동 if (map[redBall_x][redBall_y - 1] == 5) { returnValue = 1; map[redBall_x][redBall_y] = 2; } else if (map[redBall_x][redBall_y - 1] == 2) { map[redBall_x][redBall_y--] = 2; map[redBall_x][redBall_y] = 3; } // Blue 이동 if (map[blueBall_x][blueBall_y - 1] == 5) { returnValue = -1; map[redBall_x][redBall_y] = 2; } else if (map[blueBall_x][blueBall_y - 1] == 2) { map[blueBall_x][blueBall_y--] = 2; map[blueBall_x][blueBall_y] = 4; } return returnValue; } if (direction == 3) { // Red 이동 if (map[redBall_x - 1][redBall_y] == 5) { returnValue = 1; map[redBall_x][redBall_y] = 2; } else if (map[redBall_x - 1][redBall_y] == 2) { map[redBall_x--][redBall_y] = 2; map[redBall_x][redBall_y] = 3; } // Blue 이동 if (map[blueBall_x - 1][blueBall_y] == 5) { returnValue = -1; map[redBall_x][redBall_y] = 2; } else if (map[blueBall_x - 1][blueBall_y] == 2) { map[blueBall_x--][blueBall_y] = 2; map[blueBall_x][blueBall_y] = 4; } return returnValue; } } int isChanged(int prevMap[10][10], int presMap[10][10]) { for (int i = 0; i < 10; i++) { for (int ii = 0; ii < 10; ii++) { if (prevMap[i][ii] != presMap[i][ii]) { return 1; } } } return 0; } int fullUpdate(int direction) { if (direction == 0) { int repeat = 0; int returnValue = 0; do { int prevBoard[10][10] = {0}; copyBoard(prevBoard, map); int termResult = stepUpdate(0); if (termResult == 1) { returnValue += 1; } else if (termResult == -1) { returnValue -= 2; } repeat = isChanged(prevBoard, map); } while (repeat); return returnValue; } else if (direction == 1) { int repeat = 0; int returnValue = 0; do { int prevBoard[10][10] = {0}; copyBoard(prevBoard, map); int termResult = stepUpdate(1); if (termResult == 1) { returnValue += 1; } else if (termResult == -1) { returnValue -= 2; } repeat = isChanged(prevBoard, map); } while (repeat); return returnValue; } else if (direction == 2) { int repeat = 0; int returnValue = 0; do { int prevBoard[10][10] = {0}; copyBoard(prevBoard, map); int termResult = stepUpdate(2); if (termResult == 1) { returnValue += 1; } else if (termResult == -1) { returnValue -= 2; } repeat = isChanged(prevBoard, map); } while (repeat); return returnValue; } else { int repeat = 0; int returnValue = 0; do { int prevBoard[10][10] = {0}; copyBoard(prevBoard, map); int termResult = stepUpdate(3); if (termResult == 1) { returnValue += 1; } else if (termResult == -1) { returnValue -= 2; } repeat = isChanged(prevBoard, map); } while (repeat); return returnValue; } }

제출 #78353

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: