Cod sursa(job #1208789)

Utilizator RarRaresNedelcu Rares RarRares Data 16 iulie 2014 16:10:31
Problema Hashuri Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.87 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstring>


using namespace std;
#define Nmax 1001
#define INF 0x3f3f3f3f

int mini(int x,int y)
{
    if(x < y) return x;
    return y;
}

queue<pair<int,int> > Q1,Q2;
int N,M,Sx,Sy,Ex,Ey;
char A[Nmax][Nmax];
char used[Nmax][Nmax];
const int dx[5]={0,-1,0, 0,1},
          dy[5]={0, 0,1,-1,0};
short dist[Nmax][Nmax];
#define DIM 10000
char buff[DIM];
int poz = DIM - 1;

void citeste(int &numar)
{
     numar = 0;
     while (buff[poz] < '0' || buff[poz] > '9')
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
}
void read()
{
    citeste(N);citeste(M);
    citeste(Sx);citeste(Sy);
    citeste(Ex);citeste(Ey);

    ///scanf("%d%d%d%d%d%d",&N,&M,&Sx,&Sy,&Ex,&Ey);
    int xxx;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
        {
            citeste(xxx);
            A[i][j] = xxx;
            ///scanf("%d",&xxx);
            ///A[i][j] = xxx;
        }
}

int inside(int x,int y)
{
    if(1<= x && x <= N && 1 <= y && y <= M)
        return 1;
    return 0;
}

void afish(short W[Nmax][Nmax])
{
    for(int i = 1; i <= N; ++i)
    {
        for(int j =1; j <= M; ++j)
            printf("%d ",W[i][j]);
        printf("\n");
    }
}

void solve()
{
    int x = Sx,y = Sy,tip,newx,newy;
    Q1.push(make_pair(x,y));
    dist[x][y] = 1;
    while(!Q1.empty() || !Q2.empty())
    {
        while(!Q1.empty())
        {
            x = Q1.front().first;
            y = Q1.front().second;
            Q1.pop();
            used[x][y] = 1;
            tip = A[x][y];
            for(int i = 1; i <= 4; ++i)
            {
                newx = x + dx[i];
                newy = y + dy[i];
                if(inside(newx,newy) && !used[newx][newy])
                {
                    if(A[newx][newy] == tip)
                    {
                        Q1.push(make_pair(newx,newy));
                        dist[newx][newy] = dist[x][y];
                    }
                    else
                    {
                        Q2.push(make_pair(newx,newy));
                        dist[newx][newy] =(dist[newx][newy], dist[x][y] + 1);
                    }
                }
            }
        }
        if(!Q2.empty())
        {
            x = Q2.front().first;
            y = Q2.front().second;
            Q2.pop();
            Q1.push(make_pair(x,y));
        }
    }
    afish(dist);
    printf("%d\n",dist[Ex][Ey] - 1);
}

int main()
{
    freopen("padure.in","r",stdin);
    freopen("padure.out","w",stdout);

    read();
    solve();

    return 0;
}