Cod sursa(job #247935)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 24 ianuarie 2009 15:28:49
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include<stdio.h>   
#define N 105   
const int dx[]={-1,-1,-1,0,0,1,1,1};   
const int dy[]={-1,0,1,-1,1,-1,0,1};   
char s[N][N];   
int n,m,a[N][N],x0,x1,y0,y1,b[N][N];   
void bfs(int x0, int x1)   
{   
	int p=0,u=0,coada[N*N][2],x[2],y[2];   
	coada[u][0]=x0;   
	coada[u++][1]=x1;   
	a[x0][x1]=1;
	while (p!=u)   
	{   
		x[0]=coada[p][0];   
		x[1]=coada[p++][1];   
		for (int i=0; i<8; ++i)   
		{   
			y[0]=dx[i]+x[0];   
			y[1]=dy[i]+x[1];   
			if (!a[y[0]][y[1]]&&(s[y[0]][y[1]]==' '||s[y[0]][y[1]]=='J'))   
			{   
				coada[u][0]=y[0];   
				coada[u++][1]=y[1];   
				a[y[0]][y[1]]=1+a[x[0]][x[1]];   
			}   
		}   
	}   
}   
void bfs1(int x0, int x1)   
{   
	int p=0,u=0,coada[N*N][2],x[2],y[2];   
	coada[u][0]=x0;   
	coada[u++][1]=x1;   
	b[x0][x1]=1;
	while (p!=u)   
	{   
		x[0]=coada[p][0];   
		x[1]=coada[p++][1];   
		for (int i=0; i<8; ++i)   
		{   
			y[0]=dx[i]+x[0];   
			y[1]=dy[i]+x[1];   
			if (!b[y[0]][y[1]]&&(s[y[0]][y[1]]==' '||s[y[0]][y[1]]=='R'))   
			{   
				coada[u][0]=y[0];   
				coada[u++][1]=y[1];   
				b[y[0]][y[1]]=1+b[x[0]][x[1]];   
			}   
		}   
	}   
}   
void citire()   
{  
	freopen("rj.in","r",stdin);   
	freopen("rj.out","w",stdout);   
	scanf("%d%d\n",&n,&m);   
	for (int i=1; i<=n; ++i)   
	{   
		gets(1+s[i]);   
		for (int j=1; j<=m; ++j)   
			if (s[i][j]=='X')   
				{a[i][j]=-1;   b[i][j]=-1;}
			else  
                if (s[i][j]=='R')   
                {   
                x0=i; x1=j;   
                }   
                else    
                if (s[i][j]=='J')   
                {   
                        y0=i; y1=j;   
                }   
        }   
	bfs(x0,x1);   
	bfs1(y0,y1);
    int min;   
	min=1000000;  
	for (int i=1;i<=n; ++i)
	{  
        for (int j=1; j<=m; ++j) 
			if(a[i][j]==b[i][j]&&a[i][j]>0&&a[i][j]<min)
			{
				x0=i;
				y0=j;
				min=a[i][j];
			}
	}
	printf("%d %d %d ",min,x0,y0);
	/*for (int i=1;i<=n; ++i)
	{  
        for (int j=1; j<=m; ++j) 
			printf("%d ",a[i][j]);
		printf("\n");
        } 
	printf("\n\n\n");
	for (int i=1;i<=n; ++i)
	{  
        for (int j=1; j<=m; ++j) 
			printf("%d ",b[i][j]);
		printf("\n");
        } */
}   
int main()   
{   
        citire();   
        return 0;   
}