Cod sursa(job #254712)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 7 februarie 2009 13:50:40
Problema Kdrum Scor 10
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 2 Marime 1.83 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#define FIN "kdrum.in"
#define FOUT "kdrum.out"
#define N 177

using namespace std;

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

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

queue < pair <int,int> > q;
pair <int,int> b,e;
int n,r[N][N],m,v[N][N],k;

void read()
{
     int i,j;
     freopen(FIN, "r", stdin);   
     scanf("%d%d%d", &n, &m, &k);
     scanf("%d%d", &i, &j);
     r[i][j] = 1;
     b = make_pair(i,j);
     scanf("%d%d", &i, &j);
     e = make_pair(i,j);
     for (i = 1; i <= n; ++i)
         for (j = 1; j <=n ;++j)
         {
             scanf("%d", &v[i][j]);            
         }
}
void lee()
{
     int i,j;
     for (i = 0; i <= n; ++i)
         for (j = 0; j <= m; ++j)
             if (i != b.first || j != b.second)
                 if (v[i][j] != 0 )
                    r[i][j] = -1;
                 else
                    r[i][j] = -2;
     pair <int ,int> p1,p2;
     q.push(b);
     while (q.empty() == false)
     {
           p1 = q.front(); 
           if (p1 == e)
              return;
           q.pop();
           for ( i = 0; i <= 3 ; ++i)
           {
               p2 = make_pair( p1.first + dx[i], p1.second + dy[i]) ;
               if ( ( p2.first <= n && p2.first >= 1 && p2.second <= m && p2.second >= 1) && r[p2.first][p2.second] == -1)
               {
                  r[p2.first][p2.second] = r[p1.first][p1.second] + 1 ;
                  q.push(p2);       
               }   
           }
     }
}
void write()
{
     int i,j;
     freopen(FOUT, "w", stdout); 
     /*for (i = 1; i <= n; ++i)
     {
          for (j = 1; j <= m; ++j)
               printf("%d ", r[i][j]);
          printf("\n");
     }*/
     printf("%d", r[e.first][e.second]);    
}
int main()
{
    read();
    lee();
    write();    
}