// 백준 - 1726번: 로봇 // 문제이해 // 세로N, 가로M 이 주어진다. // 공장의 도면이 주어진다. 0이면 이동가능, 1이면 불가능 // 로봇의 출발지점과 바라보는 방향, 도착지점과 바라보는 방향이 주어진다. // 출발지점에서부터 도착지점까지 이동, 바라보는 방향까지의 명령 횟수를 구하기. // 로봇은 한번의 명령으로 1~3칸까지 이동 가능 // 로봇의 방향을 회전하는 경우 명령 1개 소요 #include #include #include #include int N, M; int map[101][101]; bool visit[101][101][4]; int start[3]; int end[3]; int dir[4][2] = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}}; typedef struct Que { int y, x, dir, cnt; } Queue; Queue q[1000000]; int rear, front; int turn(int start, int end) { if (start == end) return 0; int tmp = 3-start; if (tmp == end) return 2; return 1; } int move(int y, int x, int d) { int cnt = 1; int ny = y; int nx = x; if (ny == end[0] && nx == end[1]) { // printf("find end!, move = %d\n", cnt); return cnt; } for (int i=0; i<2; i++) { ny += dir[d][0]; nx += dir[d][1]; if (visit[ny][nx][d] || ny < 1 || nx < 1 || ny > N || nx > M || map[ny][nx] == 1) { // printf("move = %d\n", cnt); return cnt; } cnt++; visit[ny][nx][d] = true; if (ny == end[0] && nx == end[1]) { // printf("find end!, move = %d\n", cnt); return cnt; } } // printf("move = %d, ny = %d, nx = %d\n", cnt, y, x); return cnt; } int bfs() { int y, x, ny, nx, cnt, ncnt, d; rear = 0; front = 0; q[rear].y = start[0]; q[rear].x = start[1]; q[rear].dir = start[2]; q[rear++].cnt = 0; visit[start[0]][start[1]][start[2]] = true; while (front < rear) { y = q[front].y; x = q[front].x; d = q[front].dir; cnt = q[front++].cnt; if (y == end[0] && x == end[1]) { int tcnt = turn(d, end[2]); return cnt+tcnt; } for (int i=0; i<4; i++) { if (i == 3 - d) ncnt = cnt+2; else if (i != d) ncnt = cnt+1; else ncnt = cnt; ny = y + dir[i][0]; nx = x + dir[i][1]; if (ny >= 1 && nx >= 1 && ny <= N && nx <= M && !visit[ny][nx][i] && map[ny][nx] != 1) { visit[ny][nx][i] = true; int tmp = move(ny, nx, i); for (int j=1; j

제출 #101899

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: