CUBE-T038: Icy Floor

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

#define lli long long
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define f first
#define s second

tiii slip[1010][1010][4];
bool board[1010][1010];
int n;

void PrintSlip(){
    for(int d = 0; d < 4; ++d){
        cout << "Direction " << d << ":\n";
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= n; ++j){
                printf("(R %d, C %d, W %d) ", get<0>(slip[i][j][d]), get<1>(slip[i][j][d]), get<2>(slip[i][j][d]));
            }
            cout << "\n";
        }
        cout << "\n";
    }
}

int Dijkstra(pii s, pii e){
    vector<vector<int>> dist(n + 1, vector<int>(n + 1, 2e9));
    vector<vector<bool>> visited(n + 1, vector<bool>(n + 1, false));
    priority_queue<tiii, vector<tiii>, greater<tiii>> q; /// (dist, row, col)
    dist[s.f][s.s] = 0;
    q.push(make_tuple(dist[s.f][s.s], s.f, s.s));
    while(!q.empty()){
        int ur = get<1>(q.top());
        int uc = get<2>(q.top());
        q.pop();
        if(ur == e.f && uc == e.s){
            return dist[ur][uc];
        }
        if(visited[ur][uc]){
            continue;
        }
        visited[ur][uc] = true;
        for(int i = 0; i < 4; ++i){
            int vr = get<0>(slip[ur][uc][i]);
            int vc = get<1>(slip[ur][uc][i]);
            int w = get<2>(slip[ur][uc][i]);
            if(!visited[vr][vc] && dist[ur][uc] + w < dist[vr][vc]){
                dist[vr][vc] = dist[ur][uc] + w;
                q.push(make_tuple(dist[vr][vc], vr, vc));
            }
        }
    }
    return -1;
}

int main(){

    int x;

    scanf("%d", &n);

    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            scanf("%d", &x);
            if(x == 1){
                board[i][j] = true;
            }
        }
    }

    /// Generate Map
    for(int i = 1; i <= n; ++i){
        pii stonel = {i, 1};
        pii stoneu = {1, i};
        for(int j = 1; j <= n; ++j){
            if(board[i][j]){
                stonel = {i, j + 1};
            } else {
                slip[i][j][3] = make_tuple(stonel.f, stonel.s, j - stonel.s);
            }
            if(board[j][i]){
                stoneu = {j + 1, i};
            } else {
                slip[j][i][0] = make_tuple(stoneu.f, stoneu.s, j - stoneu.f);
            }
        }
        pii stoner = {i, n};
        pii stoned = {n, i};
        for(int j = n; j >= 1; --j){
            if(board[i][j]){
                stoner = {i, j - 1};
            } else {
                slip[i][j][1] = make_tuple(stoner.f, stoner.s, stoner.s - j);
            }
            if(board[j][i]){
                stoned = {j - 1, i};
            } else {
                slip[j][i][2] = make_tuple(stoned.f, stoned.s, stoned.f - j);
            }
        }
    }
    cout << Dijkstra({1, 1}, {n, n});

    return 0;
}