533 words
3 minutes
[BOJ] 로봇
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
2s | 128MB | (1 ≤ N, M ≤ 100) | BFS |
일단 이 문제는 방향에 대해서 visited 처리 해주면 된다. 일단 내가 BFS를 작성할 때 cost를 저장하는 배열과 비교하는 연산을 <=
으로 처리하는 것을 많이 사용한 나머지… 그대로 썼다가… 이거 찾는데 30분을 날렸다. 진짜 미치겠다. 하튼 그냥 그렇게 bfs 돌리면 풀리는 문제이다..
즐거운 ps 하셔요..ㅠㅜ
정답 코드
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
using namespace std;
using ll = long long;
int n, m;
int board[101][101];
int costBoard[101][101][4];
int dx[] = {0, 1, -1, 0, 0}, dy[] = {0, 0, 0, 1, -1};
struct pos{
int dir;
int y, x;
int pre_dir;
int cost;
int nc;
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
costBoard[i][j][0] = 1000000000;
costBoard[i][j][1] = 1000000000;
costBoard[i][j][2] = 1000000000;
costBoard[i][j][3] = 1000000000;
cin >> board[i][j];
}
}
pos target;
queue<pos> q;
int sd, sy, sx;
cin >> sy >> sx >> sd;
q.push({sd, sy, sx, 10000, 0, 0});
cin >> sy >> sx >> sd;
target = {sd, sy, sx, 10000, 0, 0};
while(!q.empty()){
pos current = q.front(); q.pop();
if(costBoard[current.y][current.x][current.dir-1] < current.cost) continue;
if(current.y == target.y && target.x == current.x) {
// 아니 min을 안 넣었네..
int result;
if(current.dir == target.dir) result = current.cost;
else result = current.cost + 1 + (abs(current.dir - target.dir) == 1 && (target.dir == 1 || target.dir == 4 || current.dir == 1 || current.dir == 4));
costBoard[current.y][current.x][target.dir-1] = min(costBoard[current.y][current.x][target.dir-1], result);
continue;
}
else costBoard[current.y][current.x][current.dir-1] = current.cost;
for(int i = 1; i < 5; i++){
int nx = current.x + dx[i];
int ny = current.y + dy[i];
if(0 < ny && ny <= n && 0 < nx && nx <= m){
if(costBoard[ny][nx][i-1] < current.cost || board[ny][nx]) continue;
int current_cost = current.cost;
int current_nc = current.nc;
current_cost+=2;
if(current.dir == i){
current_cost -=2;
current_cost+=(current.pre_dir > 100 && current.dir == i) + (current_nc >= 3);
if(current_nc >= 3) current_nc = 0;
current_nc++;
}
else if(abs(current.dir - i) == 1 && (i == 1 || i == 4 || current.dir == 1 || current.dir == 4)){
current_cost++;
current_nc = 1;
}else {
current_nc = 1;
}
// 서쪽.. 2 북 4
q.push({i, ny, nx, current.dir, current_cost, current_nc});
}
}
//
// cout << "current: " << current.y << " " << current.x << " " << current.cost << "\n";
//
// cout << "\n";
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= m; j++) {
// if(costBoard[i][j][1] == 1000000000) cout << "o ";
// else cout << costBoard[i][j][1] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
//
//
}
cout << costBoard[target.y][target.x][target.dir-1];
return 0;
}