Cod sursa(job #394457)

Utilizator RoCkyRomila RoCky Data 10 februarie 2010 22:50:21
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <iostream>
#define INF 9999
#include <string>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int a[101][101],dr[101][101],dj[101][101];
int Qr[11000][2],lir,lsr,Qj[11000][2],lij,lsj;
int dir[]={0,0,1,1,1,-1,-1,-1};
int dij[]={1,-1,0,1,-1,0,1,-1};
bool marc[101][101],marc2[101][101];
int main ()
{
	int i,n,m,j,auxi,auxj,jpj,jpi,rpj,rpi,njr,nij,njj,nir;
	string sir;
	in>>n>>m;
	getline(in,sir);
	for(i=1;i<=n;i++)
	{
		getline(in,sir);
		for(j=0;j<m;j++)
		{
			if(sir[j]==' '||sir[j]=='R'||sir[j]=='J')
			{
				a[i][j+1]=1;
				if(sir[j]=='R')
				{
					rpi=i;
					rpj=j+1;
				}
				else
				if(sir[j]=='J')
				{
					jpi=i;
					jpj=j+1;
				}
			}
			dr[i][j+1]=INF;
			dj[i][j+1]=INF;
		}
	}
	Qr[0][0]=rpi;
	Qr[0][1]=rpj;
	lsr++;
	dr[rpi][rpj]=1;
	Qj[0][0]=jpi;
	Qj[0][1]=jpj;
	dj[jpi][jpj]=1;
	lsj++;
	while(lir<lsr&&lij<lsj)
	{
		nir=Qr[lir][0];
		njr=Qr[lir][1];
		nij=Qj[lij][0];
		njj=Qj[lij][1];
		lir++;
		lij++;
		marc[nir][njr]=1;
		if(a[nir][njr]==1)
			for(i=0;i<8;i++)
			{
				auxi=nir+dir[i];
				auxj=njr+dij[i];
				if(marc[auxi][auxj]==0&&dr[auxi][auxj]>dr[nir][njr]+1&&a[auxi][auxj]==1)
				{
					dr[auxi][auxj]=dr[nir][njr]+1;
					Qr[lsr][0]=auxi;
					Qr[lsr][1]=auxj;
					lsr++;
				}
			}
		marc2[nij][njj]=1;
		if(a[nij][njj]==1)
			for(i=0;i<8;i++)
			{
				auxi=nij+dij[i];
				auxj=njj+dir[i];
				if(marc2[auxi][auxj]==0&&dj[auxi][auxj]>dj[nij][njj]+1&&a[auxi][auxj]==1)
				{
					dj[auxi][auxj]=dj[nij][njj]+1;
					Qj[lsj][0]=auxi;
					Qj[lsj][1]=auxj;
					lsj++;
				}
			}
	}
	int min=9999;
	int pozi=0,pozj=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(dr[i][j]==dj[i][j]&&dr[i][j]<min)
			{
				pozi=i;
				pozj=j;
				min=dr[i][j];
			}
	out<<min<<' '<<pozi<<' '<<pozj;
	
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++)
			if(dr[i][j]==INF)
				out<<"- ";
			else
			out<<dr[i][j]<<" ";
		out<<'\n';}
	out<<"\n\n\n";
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++)
			if(dj[i][j]==INF)
				out<<"- ";
			else
			out<<dj[i][j]<<" ";
		out<<'\n';}
	
	return 0;
}