Cod sursa(job #1565982)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 11 ianuarie 2016 18:44:35
Problema Barbar Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include  <queue>
using namespace std;
deque < pair <int, int> > q;
int n,w,m,z,t,c,d,i,j,x,y,k,b[1005][1005],v[1005][1005];
int main()
{
    ifstream f("padure.in");
    ofstream g("padure.out");
    int dx[]={-1,0,1,0};
    int dy[]={0,1,0,-1};
    f>>n>>m;
    f>>z>>t>>c>>d;
    q.push_back(make_pair(z,t));
    for(i=1; i<=n; i++)
    for(j=1; j<=m; j++)
    {
        f>>v[i][j];
        b[i][j]=9000005;
    }
    b[z][t]=0;
    for(i=0; i<=n+1; i++)
    {
        b[i][0]=-1;
        b[i][m+1]=-1;
    }
    for(i=0; i<=m+1; i++)
    {
        b[i][0]=-1;
        b[i][n+1]=-1;
    }
    while(!q.empty())
    {
        i=q.front().first;
        j=q.front().second;
        q.pop_front();
        for(k=0; k<4; k++)
        {
            x=i+dx[k];
            y=j+dy[k];
            if(v[x][y]==v[i][j]&&b[x][y]>b[i][j])
            {
                w = b[x][y]=b[i][j];
                if (!q.empty() && w <= b[q.front().first][q.front().second])
                q.push_front(make_pair(x,y));
                else q.push_back(make_pair(x,y));
            }
            else
            if(b[x][y]>b[i][j]+1)
            {
                w = b[x][y]=b[i][j]+1;
                if (!q.empty() && w <= b[q.front().first][q.front().second])
                q.push_front(make_pair(x,y));
                else q.push_back(make_pair(x,y));
            }
        }
    }
    g<<b[c][d]<<'\n';
    f.close(); g.close();
    return 0;
}