2Bk PROG1149

#include<stdio.h>
#include<queue>
using namespace std;

int arr[1010][1010];
int n;
int startI[2];
int startJ[2];
int ans = 1e9;
struct edge{
    int charm;
    int maxc;
    int y;
    int x;
    bool operator<(const edge& rhs)const
    {
        return charm > rhs.charm;
    }
};

void findmin(){
    int move[4][2] = {{0,-1},{0,1},{1,0},{-1,0}};
    priority_queue<edge> pq;
    pq.push({0,0,startI[0],startJ[0]});
    bool visited[n][n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            visited[i][j] = false;
        }
    }
    while(!pq.empty()){
        int charm = pq.top().charm;
        int lmax = pq.top().maxc;
        int nowY = pq.top().y;
        int nowX = pq.top().x;
        pq.pop();
        if(!visited[nowY][nowX]){
        //  printf("Test y : %d , x : %d\n",nowY,nowX);
            if(nowY == startI[1] && nowX == startJ[1]){
        //      printf("Test %d\n",lmax);
                ans = min(ans,lmax);
            }else{
                visited[nowY][nowX] = true;
                for(int i=0;i<4;i++){
                    int nY = nowY+move[i][0];
                    int nX = nowX+move[i][1];
                    if(0 <= nY && nY < n  &&  0 <= nX && nX < n){
                        if(!visited[nY][nX]){
                            int nextmax;
                            if(arr[nowY][nowX] != 0){
                                nextmax = max(arr[nY][nX],lmax);
                            }else{
                                nextmax = arr[nY][nX];
                            }
                        //  printf("Test %d\n",nextmax);
                            pq.push({arr[nY][nX] , nextmax , nY , nX});
                        }
                    }
                }
            }

        }
    }
}

int main()
{
    scanf("%d",&n);
    int stc = 0;
//  priority_queue<int,vector<int> ,greater<int> > q;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&arr[i][j]);
            if(arr[i][j] == 0){
                startI[stc] = i;
                startJ[stc] = j;
                stc++;
            }else{
    //          q.push(arr[i][j]);
            }
        }
    }
//  printf("start y : %d , x : %d\nstop y : %d , x : %d\n",startI[0],startJ[0],startI[1],startJ[1]);
    findmin();
    printf("%d",ans);
}