Cod sursa(job #755158)

Utilizator manciu_ionIon Manciu manciu_ion Data 4 iunie 2012 20:31:19
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
/*#include <fstream.h>
#define InFile "rj.in"
#define OutFile "rj.out"
#define NMax 102
#define NV 8

int n, m, xr, yr, xj, yj;
int dl[NV]={0, 1, 0, -1, -1, 1, -1, 1};
int dc[NV]={1, 0, -1, 0, -1, 1, 1, -1};
char l[NMax][NMax];
int r[NMax][NMax];

ifstream f(InFile);

void citire(void);
void afisare(int [NMax][NMax]);
void parcurge(int, int, int[NMax][NMax]);

int main()
{ int j[NMax][NMax];
  citire();
  parcurge(xr, yr, r);
  parcurge(xj, yj, j);
  afisare(j);
  return 0;
}

void citire(void)
{
 int i, k;
 char c;
 f>>n>>m;
 for (i=0; i<=n+1; i++) l[i][0]=l[i][m+1]='X';
 for (i=0; i<=m+1; i++) l[0][i]=l[n+1][i]='X';
 f.get(c);
 for (i=1; i<=n; i++)
	 {for (k=1; k<=m; k++)
	      {f.get(c); l[i][k]=c;
	      if (l[i][k]=='R') {xr=i; yr=k; l[i][k]=' ';}
	      if (l[i][k]=='J') {xj=i; yj=k; l[i][k]=' ';}
	      }
	 f.get(c);}
  f.close();
}

void parcurge(int x0, int y0, int d[NMax][NMax])
{
struct Punct {int l, c;} C[NMax*NMax], p;
int inc=0, sf=0, i, k;
for (i=0; i<=n+1; i++)
       for (k=0; k<=m+1; k++) d[i][k]=-1;
C[0].l=x0; C[0].c=y0; d[x0][y0]=1;
while (inc<=sf)
	 {
	  p=C[inc++];
	  for (i=0; i<NV; i++)
		 if (l[p.l+dl[i]][p.c+dc[i]]==' ' && d[p.l+dl[i]][p.c+dc[i]]==-1)
			   {
			    d[p.l+dl[i]][p.c+dc[i]]=1+d[p.l][p.c];
			    C[++sf].l=p.l+dl[i];
			    C[sf].c=p.c+dc[i];
			    }
	   }
}

void afisare(int j[NMax][NMax])
{
ofstream f(OutFile);
int tmin=NMax*NMax+5, xmin=-1, ymin=-1, i, k;
for (i=1; i<=n; i++)
     for (k=1; k<=m; k++)
	if (r[i][k]==j[i][k])
	      if (r[i][k]<tmin && r[i][k]!=-1)
		 {tmin=r[i][k]; xmin=i; ymin=k;}
f<<tmin<<' '<<xmin<<' '<<ymin<<'\n';
f.close();
}

*/
#include<cstdio>
using namespace std;
typedef struct{int x,y;}per;
per p[10025],q[10025];
int v[105][105],w[105][105];
int main()
{
freopen("rj.in","r",stdin);
freopen("rj.out","w",stdout);
int d,s,n,m,i,j,x1,y1,x2,y2,x3,y3,min=1000000;
int dx[]={0,-1,-1,-1,0,1,1,1,0};
int dy[]={0,-1,0,1,1,1,0,-1,-1};
char c;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)for(j=1;j<=m;j++)
{
scanf("%c",&c);
if(c=='\n')scanf("%c",&c);
if(c==' ')w[i][j]=v[i][j]=0;
if(c=='X')w[i][j]=v[i][j]=1;
if(c=='R'){x2=i;y2=j;}
if(c=='J'){x3=i;y3=j;}
}
for(i=0;i<=m+1;i++) {v[n+1][i]=-1; w[n+1][i]=-1; v[0][i]=-1; w[0][i]=-1;}
for(i=0;i<=n+1;i++) {w[i][0]=-1; v[i][0]=-1; w[i][m+1]=-1; v[i][m+1]=-1;}
d=s=1;v[x2][y2]=1;
p[d].x=x2;
p[d].y=y2;
while(s<=d)
{
x1=p[s].x;
y1=p[s].y;
for(i=1;i<=8;i++)if(v[x1+dx[i]][y1+dy[i]]==0)
{
d++;
p[d].x=x1+dx[i];
p[d].y=y1+dy[i];
v[p[d].x][p[d].y]=v[x1][y1]+1;
}
s++;
}
s=d=1;w[x3][y3]=1;
q[d].x=x3;
q[d].y=y3;
while(s<=d)
{
x1=q[s].x;
y1=q[s].y;
for(i=1;i<=8;i++)if(w[x1+dx[i]][y1+dy[i]]==0)
{
d++;
q[d].x=x1+dx[i];
q[d].y=y1+dy[i];
w[q[d].x][q[d].y]=w[x1][y1]+1;
}
s++;
}
for(i=1;i<=n;i++){for(j=1;j<=m;j++)if(v[i][j]==w[i][j]&&min>v[i][j]&&v[i][j]!=1&&v[i][j]!=0){min=v[i][j];x2=i;y2=j;}}
printf("%d %d %d",min,x2,y2);
return 0;
}