Cod sursa(job #2390163)

Utilizator PredaBossPreda Andrei PredaBoss Data 27 martie 2019 20:11:41
Problema Matrice 2 Scor 35
Compilator cpp-64 Status done
Runda cel_mai_mare_olimpicar_2019_oni2009_zi2 Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("matrice2.in");
ofstream fout("matrice2.out");
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,q;
int ap[105][105];
int matrix[105][105];
pair<int,int>start,finish;
int main()
{
    fin>>n>>q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            fin>>matrix[i][j];
    for(int t=1;t<=q;t++)
    {
        fin>>start.first>>start.second>>finish.first>>finish.second;
        priority_queue<pair<int,pair<int,int> > >pq;
        pq.push({matrix[start.first][start.second],{start.first,start.second}});
        while(!pq.empty())
        {
            int val=pq.top().first;
            int x=pq.top().second.first;
            int y=pq.top().second.second;
            pq.pop();
            if(ap[x][y]==t)continue;
            ap[x][y]=t;
            if(x==finish.first && y==
               finish.second)
            {
                fout<<val<<"\n";
                break;
            }
            for(int g=0;g<4;g++)
            {
                int x1=x+dx[g];
                int y1=dy[g]+y;
                if(x1<1 || x1>n || y1<1 || y1>n || ap[x1][y1]==t)continue;
                pq.push({min(val,matrix[x1][y1]),{x1,y1}});
            }
        }
    }
    return 0;
}