백준
백준 1726 로봇
콩순이냉장고
2021. 12. 11. 00:53
문제 URL : https://www.acmicpc.net/problem/1726
1726번: 로봇
많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는
www.acmicpc.net
문제접근법 : bfs문제인데
첫번째 : 이동을 먼저 1~3칸까지 해보고 1이 안된다면 더이상 움직이지 않습니다. 벽을 뚫고 지나갈순없으니까
그리고 왼쪽또는 오른쪽으로 회전 하면서 bfs를 탐색하면 되기때문에 어려운 문제는 아닙니다.
그치만 처음 풀었을대 3~1칸으로 움직이면서 탐색했을땐 틀렸네요.. 3칸을 움직일수있는지 확인해보고 탐색했는데 생각해보니 3칸움직일수있는지 확인하면서 2칸도 움직이는지 확인을 했어햐했는데 그걸안해서 틀린듯합니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int n, m;
int board[101][101];
int sy, sx, sdir;
int fy, fx, fdir;
void change(int& dir) {
if (dir == 4)
dir = 0;
else if (dir == 1)
dir = 1;
else if (dir == 3)
dir = 2;
else if (dir == 2)
dir = 3;
}
void input() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
cin >> sy >> sx >> sdir;
cin >> fy >> fx >> fdir;
sy--, sx--, fy--, fx--;
change(sdir);
change(fdir);
}
bool isrange(int y, int x) {
return 0 <= y && y < n && 0 <= x && x < m;
}
int bfs() {
int check[100][100][4] = { 0 };
queue<tuple<int, int, int, int>> q;
q.push({ sy,sx,sdir ,0 });
check[sy][sx][sdir] = 1;
while (!q.empty()) {
int y, x, dir, cnt;
tie(y, x, dir, cnt) = q.front();
q.pop();
if (y == fy && x == fx && dir == fdir)
return cnt;
for (int i = 1; i <= 3; i++) {
int ny = y + dy[dir] * i;
int nx = x + dx[dir] * i;
if (!isrange(ny, nx))break;
if (board[ny][nx])break;
if (check[ny][nx][dir] == 0) {
q.push({ ny,nx,dir,cnt + 1 });
check[ny][nx][dir] = 1;
}
}
for (int i : {1, -1}) {
int ndir = (4 + dir + i) % 4;
if (check[y][x][ndir] == 0) {
q.push({ y,x,ndir,cnt + 1 });
check[y][x][ndir] = 1;
}
}
}
return -1;
}
void solve() {
cout << bfs() << "\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤질무이든 댓글은 언제나 환영입니다.