Cod sursa(job #88085)

Utilizator c_sebiSebastian Crisan c_sebi Data 30 septembrie 2007 11:44:36
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <stdio.h>

int nl, nc, a[102][102], b[102][102], ij, jj, ir, jr, min=30000;


void drum (int a[][102], int i0, int j0)
{

	struct Coada {	int l, c, d;} C[5050], u, v;
	int di[]={-1, -1, 0, 1, 1, 1, 0, -1}, dj[]={0, -1, -1, -1, 0, 1, 1, 1};
	int SfC=0, IncC=0, k;
	C[SfC].l=i0; C[SfC].c=j0; C[SfC].d=a[i0][j0];
	while (IncC <= SfC)
		{
			u=C[IncC++];
			for (k=0; k<8; k++)
				{
					v.l=u.l+di[k]; v.c=u.c+dj[k];
					if (a[v.l][v.c]==-1)
						{
							v.d=u.d+1;
							a[v.l][v.c]=v.d;
							C[++SfC]=v;
						}
				}
		}
}

int main()
{
	char s[130];
	int i, j;
	FILE *f=fopen("rj.in", "r");
	fscanf(f, "%d %d\n", &nl, &nc);
	for (i=1; i<=nl; i++)
		{
			fgets(s+1, 130, f);
			for(j=1; j<=nc; j++)
				if (s[j]==' ') a[i][j]=b[i][j]=-1;
				else if (s[j]=='J') { a[i][j]=1; b[i][j]=0; ij=i; jj=j; }
				else if (s[j]=='R') { a[i][j]=0; b[i][j]=1; ir=i; jr=j; }
		}
	fclose(f);
	drum (a, ij, jj);
	drum (b, ir, jr);
	for (i=1; i<=nl; i++)
		for (j=1; j<=nc; j++)
			if (a[i][j] && a[i][j]!=-1 && a[i][j]==b[i][j] && a[i][j]<min)
				{min=a[i][j]; ir=i; jr=j; }
	FILE *g=fopen("rj.out", "w");
	fprintf(g, "%d %d %d\n", min, ir, jr);
	fclose(g);
	return 0;
}