Cod sursa(job #467792)

Utilizator nickyyLal Daniel Emanuel nickyy Data 30 iunie 2010 17:31:20
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <stdio.h>
#define max 101
#define inf 1000000
using namespace std;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
struct elem
	{int l,c,d;		}cr[max*max],cj[max*max];
int a[max][max],n,m;
	
	void read(void)
	{FILE *fin=fopen("rj.in","r");
	 int i,j,k;
	 
	 fscanf(fin,"%d%d",&n,&m);
	 for(i=1;i<=n;i++)
		 {k=fgetc(fin); 
		  for(j=1;j<=m;j++)
			{k=fgetc(fin);
			 if(k=='X') a[i][j]=inf;
			 else if(k=='R' || k=='J')
					if(k=='R')cr[0].l=i, cr[0].c=j, cr[0].d=1, a[i][j]=1;
						else cj[0].l=i, cj[0].c=j, cj[0].d=-1, a[i][j]=-1;
			}
		 }
	 fclose(fin);
	}
	
	void bord(void)
	{int i;
	 for(i=0;i<=n+1;i++) a[i][0]=a[i][m+1]=inf;
	 for(i=1;i<=m;i++) a[0][i]=a[n+1][i]=inf;
	}
	
	void solve_write(void)
	{int ic1=0,sf1=0,ic2=0,sf2=0,k,ok=0,minl=102,minc=102,min;
	 FILE *fout=fopen("rj.out","w");
	 elem x,y;
	 
	 x=cr[0]; a[x.l][x.c]=1;
	 x=cj[0]; a[x.l][x.c]=-1;
	 while(!ok)
		{do
			{x=cr[ic1++]; 
			 for(k=0;k<8;k++)
				{y.l=x.l+dx[k]; y.c=x.c+dy[k]; y.d=x.d+1;
				 if(a[y.l][y.c]==0) cr[++sf1]=y, a[y.l][y.c]=y.d;
				}
			}while(cr[ic1].d==cr[ic1-1].d);
		do
			{x=cj[ic2++];
			 for(k=0;k<8;k++)
				{y.l=x.l+dx[k]; y.c=x.c+dy[k]; y.d=x.d-1;
				 if(a[y.l][y.c]==-y.d) 
					 {ok=1; 
					  if(minl>y.l) minl=y.l,min=-y.d,minc=y.c;
					  else if(minl==y.l && minc>y.c) minc=y.c,min=-y.d;	
					 }
				 else if(a[y.l][y.c]==0) cj[++sf2]=y, a[y.l][y.c]=y.d;
				}
			}while(cj[ic2].d==cj[ic2-1].d);
		}
	 fprintf(fout,"%d %d %d",min,minl,minc);
	 fclose(fout);
	}
	
int main(void)
{read();
 bord();
 solve_write();
 return 0;
}