Cod sursa(job #254633)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 7 februarie 2009 13:22:15
Problema Kdrum Scor 20
Compilator c Status done
Runda Stelele Informaticii 2009, clasele 9-10, ziua 2 Marime 1.6 kb
#include<stdio.h>
#include<string.h>

struct punct{

		int x;
		int y;
		int pas;
	};


int n,m,mat[50][50];


int drum_minim(int x1,int y1,int x2,int y2)
{
	struct punct coada[2500];
	int x,y;
	struct punct pct,nextpct;
	int head,tail,minim;
	int viz[50][50];

	pct.x=x1;
	pct.y=y1;
	pct.pas=0;
	head=0;
	tail=0;
	coada[head++]=pct;
	memset(viz,0,2500*sizeof(int));

	while(head!=tail)
	{
		if(pct.x==x2 && pct.y==y2)
		{
			minim=pct.pas;
			break;
		}	


		if(pct.x>0 && mat[pct.x-1][pct.y]>0 && viz[pct.x-1][pct.y]==0)
		{
			nextpct.x=pct.x-1;
			nextpct.y=pct.y;
			nextpct.pas=pct.pas+1;
			coada[head++]=nextpct;
			viz[nextpct.x][nextpct.y]=1;
		}

		if(pct.x<n && mat[pct.x+1][pct.y]>0 && viz[pct.x+1][pct.y]==0)
		{
			nextpct.x=pct.x+1;
			nextpct.y=pct.y;
			nextpct.pas=pct.pas+1;
			coada[head++]=nextpct;
			viz[nextpct.x][nextpct.y]=1;
		}

		if(pct.y>0 && mat[pct.x][pct.y-1]>0 && viz[pct.x][pct.y-1]==0)
		{
			nextpct.x=pct.x;
			nextpct.y=pct.y-1;
			nextpct.pas=pct.pas+1;
			coada[head++]=nextpct;
			viz[nextpct.x][nextpct.y]=1;
		}
		if(pct.y<m && mat[pct.x][pct.y+1]>0 && viz[pct.x][pct.y+1]==0)
		{
			nextpct.x=pct.x;
			nextpct.y=pct.y+1;
			nextpct.pas=pct.pas+1;
			coada[head++]=nextpct;
			viz[nextpct.x][nextpct.y]=1;
		}

		tail++;
		pct=coada[tail];
	}
	return minim;
}


int main()
{
	FILE *f;
	int k,x1,y1,x2,y2;
	int i,j;

	f=fopen("kdrum.in","r");
	fscanf(f,"%i%i%i",&n,&m,&k);
	fscanf(f,"%i%i%i%i",&x1,&y1,&x2,&y2);
	
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
			fscanf(f,"%i",&mat[i][j]);

	fclose(f);
	f=fopen("kdrum.out","w");
	fprintf(f,"%i",drum_minim(x1-1,y1-1,x2-1,y2-1)+1);
	fclose(f);
	return 0;
}