Cod sursa(job #81073)

Utilizator ScrazyRobert Szasz Scrazy Data 31 august 2007 11:45:22
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <stdio.h>
#define NMax 102

const int d1[8] = { 0, 0, 1, -1, 1, -1, 1, -1 };
const int d2[8] = { 1, -1, 0, 0, 1, -1, -1, 1 };

int r[NMax][NMax], ju[NMax][NMax];
int n, m, rx, ry, jx, jy;

int posibil(int x, int y)
{
    return 0<x && x<=n && 0<y && y<=n;
}

void lee(int x0, int y0, int a[NMax][NMax])
{
    int v[NMax*NMax][2]={0}, start=0, finish=0, i, j;

    v[0][0]=x0;
    v[0][1]=y0;
    a[x0][y0]=1;

    while (start<=finish)
    {
	i=v[start][0];
	j=v[start][1];

	for (int k=0; k<=7; ++k)
	    if (posibil(i+d1[k],j+d2[k]))
	    {
		if (a[i+d1[k]][j+d2[k]]==0 ||
		    a[i+d1[k]][j+d2[k]]>a[i][j]+1)
		{
		    a[i+d1[k]][j+d2[k]]=a[i][j]+1;
		    v[++finish][0]=i+d1[k];
		    v[finish][1]=j+d2[k];
		}
	    }
	++start;
    }

}

void read()
{
    char ch;
    scanf("%d %d", &n, &m);
    getc(stdin);
    for (int i=1; i<=n; ++i)
    {
	//fgets(ch, sizeof(ch), stdin); 
	
	getc(stdin);
	for (int j=1; j<=m; ++j)
	{
	    //sanf("%c", &ch);
	    ch = getc(stdin);

	    switch (ch)
	    {
		case ' ' : r[i][j]=0; break;
		case 'X' : r[i][j]=-1; break;
		case 'R' : r[i][j]=0; rx=i; ry=j; break;
		case 'J' : r[i][j]=0; jx=i; jy=j; break;
	        case '\n': --j;
	    }
	}
	//getc(stdin);
    }
    for (int i=1; i<=n; ++i)
	for (int j=1; j<=m; ++j)
	    ju[i][j]=r[i][j];
}    
/*
void kiir(int a[NMax][NMax])
{
    for (int i=1; i<=n; ++i)
    {
	for (int j=1; j<=m; ++j)
	    fprintf(stderr,"%d ", a[i][j]);
	fprintf(stderr,"\n"); 
    }
} 
*/

int main()
{
    freopen("rj.in","r",stdin);
    freopen("rj.out","w",stdout);

    int tmin, mini, minj;

    read();
    //kiir(r);
    lee(rx, ry, r);
    lee(jx, jy, ju);

    //kiir(r);
    //fprintf(stderr,"\n");
    //kiir(ju);

    tmin=NMax*NMax+1;
    for (int i=1; i<=n; ++i)
	for (int j=1; j<=m; ++j)
	    if (r[i][j]==ju[i][j])
		if (r[i][j]<tmin && r[i][j] != -1 && r[i][j] != 0) 
		{
		    tmin=r[i][j]; 
		    mini=i;
		    minj=j;
		} 
    printf("%d %d %d", tmin, mini, minj);

    fclose(stdin);
    fclose(stdout);

    return 0;

}