-
https://www.acmicpc.net/problem/1726
1726번: 로봇
많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다. 명령 1. Go k - k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir - dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 공장 내 궤
www.acmicpc.net
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117#include<iostream>#include<queue>#include<utility>using namespace std;struct robot {int x, y, dir, cnt;robot(int x, int y, int dir, int cnt) {this->x = x;this->y = y;this->dir = dir;this->cnt = cnt;}};int m, n, ex, ey, ed;int map[101][101];int dist[100][100];bool dos[100][100][2];int ans = 987654321;robot rb = robot(0, 0, 0, 0);int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };int main() {ios_base::sync_with_stdio(0);cin.tie(0);cin >> m >> n;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {cin >> map[i][j];}}int a, b, c;cin >> a >> b >> c;rb = robot(a, b, c - 1, 0);cin >> ex >> ey >> ed;ed--;queue<robot > q;q.push(rb);while (!q.empty()) {int x = q.front().x;int y = q.front().y;int d = q.front().dir;int cnt = q.front().cnt;//cout << x << ' ' << y << ' ' << d << ' ' << cnt << '\n';q.pop();if (ex == x && ey == y && ed == d) {ans = cnt; break;}if (ex == x && ey == y) {for (int i = 0; i < 4; i++) {if (d == 0 && i == 1 && i == ed) {ans = ans > cnt + 2 ? cnt + 2 : ans;break;}if (d == 1 && i == 0 && i == ed) {ans = ans > cnt + 2 ? cnt + 2 : ans;break;}if (d == 2 && i == 3 && i == ed) {ans = ans > cnt + 2 ? cnt + 2 : ans;break;}if (d == 3 && i == 2 && i == ed) {ans = ans > cnt + 2 ? cnt + 2 : ans;break;}if (i == ed) {ans = ans > cnt + 1 ? cnt + 1 : ans;break;}}}int sx = x; int sy = y;for (int i = 0; i < 3; i++) {sx += dx[d]; sy += dy[d];int nx = sx; int ny = sy;if (nx <= 0 || nx > m || ny <= 0 || ny > n)continue;if (map[nx][ny] == 1) break;if (dist[nx][ny] == 0) {dist[nx][ny] = cnt + 1;q.push(robot(nx, ny, d, cnt + 1));}else if (dist[nx][ny] > cnt + 1) {dist[nx][ny] = cnt + 1;q.push(robot(nx, ny, d, cnt + 1));}}for (int i = 0; i < 4; i++) {int nx = x + dx[i]; int ny = y + dy[i];if (nx <= 0 || nx > m || ny <= 0 || ny > n)continue;if (i == d) continue;if (dos[x][y][1] == false) {if (d == 0 && i == 1) q.push(robot(x, y, i, cnt + 2));else if (d == 1 && i == 0)q.push(robot(x, y, i, cnt + 2));else if (d == 2 && i == 3)q.push(robot(x, y, i, cnt + 2));else if (d == 3 && i == 2)q.push(robot(x, y, i, cnt + 2));else q.push(robot(x, y, i, cnt + 1));}}dos[x][y][1] = true;}/*for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {cout << dist[i][j] << ' ';}cout << '\n';}*/cout << ans << '\n';return 0;}http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color ScripterBFS문제, 근데 함정이 좀 많다.
직진할때, 갈수없는곳으로가면 멈춰야하고, 회전하는 움직임일때는, 뒤로가는방향도 포함이될순있는데, 이때 가중치가 2가된다는것, 이것을 확인하기위해서 그냥 bool배열을 처음에 3차원으로만들었다.
2차원으로도 충분하며, 돌때만 확인해주면된다.