Cod sursa(job #489590)

Utilizator nautilusCohal Alexandru nautilus Data 2 octombrie 2010 22:46:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include<fstream>
#include<queue>
#define dmax 110
#define inf 100000
using namespace std;

int n,m;
int a[3][dmax][dmax];
int dx[8]={-1,0,1,0,-1,-1,1,1}, dy[8]={0,-1,0,1,-1,1,-1,1};
queue<int> qx,qy;

void lee(int startx, int starty, int tip)
{
 int curentx,curenty,curentlung;
 int k;
	
 qx.push(startx); qy.push(starty);
 while (qx.size())
	 {
	  curentx=qx.front(); curenty=qy.front(); curentlung=a[tip][curentx][curenty];
	  for (k=0; k<8; k++)
		 if (/*a[tip][curentx+dx[k]][curenty+dy[k]]!=-1 && */(a[tip][curentx+dx[k]][curenty+dy[k]]>curentlung+1 || a[tip][curentx+dx[k]][curenty+dy[k]]==0))
		     {
			  a[tip][curentx+dx[k]][curenty+dy[k]]=curentlung+1;
			  qx.push(curentx+dx[k]); qy.push(curenty+dy[k]);
			 }
	  qx.pop(); qy.pop();
	 }
}

 
void afisare()
{
 int i,j,maximx,maximy;
 long maxim=inf;
	
 for (i=1; i<=n; i++)
	 for (j=1; j<=m; j++)
		 if (a[1][i][j]==a[2][i][j] && a[1][i][j]>0)
			 if (a[1][i][j]<maxim)
				 {maxim=a[1][i][j]; maximx=i; maximy=j;} else
				 if (a[1][i][j]==maxim)
					 if (maximx>i)
					 {maximx=i; maximy=j;}

 ofstream fout("rj.out");
 
 fout<<maxim<<" "<<maximx<<" "<<maximy;
 
 fout.close();
}

int main()
{
 int i,j,rx,ry,jx,jy;
 char s[dmax];
	
 ifstream fin("rj.in");
 fin>>n>>m;
 fin.get();
 for (i=1; i<=n; i++)
	 {
	  fin.get(s,200);
	  fin.get();
	  for (j=0; j<strlen(s); j++)
		  if (s[j]=='X')
			  a[1][i][j+1]=a[2][i][j+1]=-1; else
			  if (s[j]=='R')
				  {rx=i; ry=j+1;} else
				  if (s[j]=='J')
					  {jx=i; jy=j+1;}
		 }

 for (i=0; i<=n+1; i++)
	 a[1][i][0]=a[2][i][0]=a[1][i][m+1]=a[2][i][m+1]=-1;
 for (i=0; i<=m+1; i++)
	 a[1][0][i]=a[2][0][i]=a[1][n+1][i]=a[2][n+1][i]=-1;
 
 a[1][rx][ry]=a[2][jx][jy]=1;
 
 lee(rx,ry,1);
 lee(jx,jy,2);
 
 afisare();
 
 fin.close();
 return 0;
}