Cod sursa(job #254399)

Utilizator sigridMaria Stanciu sigrid Data 7 februarie 2009 11:52:44
Problema Kdrum Scor 20
Compilator cpp Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 2 Marime 1.47 kb
#include<fstream.h>
#define dim 51


ifstream f("kdrum.in");
ofstream g("kdrum.out");

int mat[dim][dim],min[dim][dim],c[dim*dim][2];
int n,m,k;


int main()
{

int i,j,sx,sy,fx,fy,ok,x,y,prim,ultim;

f>>n>>m>>k;
f>>sx>>sy>>fx>>fy;

for(i=1;i<=n;i++)
 for(j=1;j<=m;j++)
  {
    f>>mat[i][j];

    min[i][j]=32000;
  }

f.close();

ok=0;

prim=ultim=1;
c[prim][0]=sx;
c[prim][1]=sy;
min[sx][sy]=1;

while( (!ok) && (prim<=ultim) )
{
 //extrag elementul curent din coada
 x=c[prim][0];
 y=c[prim][1];

 //parcurg cele 4 directii
   //.1: x-1 y
  if(mat[x-1][y])
    {
     if(min[x-1][y] > (min[x][y]+1) )
	{ultim++;
	 c[ultim][0]=x-1;
	 c[ultim][1]=y;

	 min[x-1][y]=min[x][y]+1;

	 if( ((x-1)==fx) && (y==fy) ) ok=1;
	}

    }

   //.2: x y+1
  if(mat[x][y+1])
    {
     if(min[x][y+1] > (min[x][y]+1) )
	{ultim++;
	 c[ultim][0]=x;
	 c[ultim][1]=y+1;

	 min[x][y+1]=min[x][y]+1;

	 if( (x==fx) && ((y+1)==fy) ) ok=1;
	}

    }

   //.3: x+1 y
  if(mat[x+1][y])
    {
     if(min[x+1][y] > (min[x][y]+1) )
	{ultim++;
	 c[ultim][0]=x+1;
	 c[ultim][1]=y;

	 min[x+1][y]=min[x][y]+1;

	 if( ((x+1)==fx) && (y==fy) ) ok=1;
	}

    }

   //.4: x y-1
  if(mat[x][y-1])
    {
     if(min[x][y-1] > (min[x][y]+1) )
	{ultim++;
	 c[ultim][0]=x;
	 c[ultim][1]=y-1;

	 min[x][y-1]=min[x][y]+1;

	 if( (x==fx) && ((y-1)==fy) ) ok=1;
	}

    }

  prim++;

}


g<<min[fx][fy]<<'\n';

g.close();
return 0;
}