[BOJ] 로봇

#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;
}