CUBE-038: Icy Floor

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int,pair<int,int>>;
int fl[1001][1001];
bool visited[1001][1001];
int n;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
const int INF = 1e9;

bool chpos(int x,int y){
    return x>=1 and x<=n and y>=1 and y<=n;
}

pii walk(int x,int y,int dxt,int dyt,int dis){
    while(chpos(x+dxt,y+dyt) and fl[x+dxt][y+dyt]!=-1){
        x += dxt;
        y += dyt;
        dis++;
    }
    return {dis,{x,y}};
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&fl[i][j]);
            if(fl[i][j] == 1)
                fl[i][j] = -1;
        }
    }
    priority_queue<pii,vector<pii>,greater<pii> > Q;
    Q.push({0,{1,1}});
    while(!Q.empty()){
        int x = Q.top().second.first;
        int y = Q.top().second.second;
        int d = Q.top().first;
        Q.pop();
        if(x==n and y==n){
            printf("%d",d);
            break;
        }
        if(visited[x][y])
            continue;
        visited[x][y] = true;
        for(int i=0;i<4;i++){
            if(chpos(x+dx[i],y+dy[i])){
                Q.push(walk(x,y,dx[i],dy[i],d));
            }
        }
    }
}