Cod sursa(job #947400)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 7 mai 2013 12:49:07
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;
queue <pair <int, int> > Q;
int n, m, ist, jst, ifn, jfn, a[1005][1005], l[1005][1005];

const int dx[] = { -1, 0, 0, 1};
const int dy[] = {  0,-1, 1, 0};

ifstream cin("padure.in");
ofstream cout("padure.out");
char parse[100000], *now;

inline void verify()
{
    if ( *now == 0 )
    {
        cin.get(parse, sizeof(parse), '\0');
        now = parse;
    }
}
int get()
{
    while (*now < '0' || *now > '9')
    {
        ++now;
        verify();
    }
    int num = 0;
    while (*now >= '0' && *now <= '9')
    {
        num = num * 10 + (*now - '0');
        ++now;
        verify();
    }
    return num;
}
int main()
{


    cin>>n>>m;
    cin>>ist>>jst;
    cin>>ifn>>jfn;
    cin.get();
    now = parse;
    verify();
    for(int i = 1 ; i <= n ; ++ i)
        for(int j = 1 ; j <= m ; ++ j)
            a[i][j]=get();
    for( Q.push(make_pair(ist, jst)) ; !Q.empty(); Q.pop())
    {
        int x = Q.front().first;
        int y = Q.front().second;
        for(int i = 0 ; i < 4; ++ i)
        {
            int xnou = x + dx[i];
            int ynou = y + dy[i];
            if( xnou >= 1 && xnou <= n  &&  ynou>=1 && ynou<=m )
            {
                if(a[xnou][ynou] == a[x][y])
                {
                    if(l[xnou][ynou] > l[x][y] || l[xnou][ynou] == 0)
                        l[xnou][ynou]=l[x][y], Q.push(make_pair(xnou, ynou));
                }
                else if(l[xnou][ynou] > l[x][y] + 1 || l[xnou][ynou] == 0)
                    l[xnou][ynou] = l[x][y] + 1 , Q.push(make_pair(xnou, ynou));

            }
        }
    }
    cout<<l[ifn][jfn]<<"\n";
    cin.close();
    cout.close();
    return 0;
}