Cod sursa(job #661248)

Utilizator bogdan353Costea Bogdan bogdan353 Data 14 ianuarie 2012 10:15:39
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<fstream>
#include<queue>
using namespace std;

int n,m,d1[8]={0,0,1,-1,1,1,-1,-1},d2[8]={1,-1,0,0,1,-1,1,-1},rom[104][104],jul[104][104];
queue<pair <char,char> >Q;
bool mat[104][104];
char x[104][104];

void parcurg(int pi, int pj, int ti, int tj, int cos[104][104])
{
	int a,b;
	
	cos[pi][pj]=1;
	Q.push(make_pair(pi,pj));
	
	while(!Q.empty())
	{
		a=Q.front ().first;
		b=Q.front ().second;
		
		if(a==ti && b==tj) break;
		
		for(int i=0;i<8;i++)
		{
			if(mat[a+d1[i]][b+d2[i]]==1) continue;
			
			if(x[a+d1[i]][b+d2[i]]==' ')
			{
				mat[a+d1[i]][b+d2[i]]=1;
				cos[a+d1[i]][b+d2[i]]=cos[a][b]+1;
				Q.push(make_pair(a+d1[i],b+d2[i]));
			}
		}
		Q.pop();
	}
}
	

int main()
{
	int pri,prj,pji,pjj;
	ifstream f("rj.in");
	ofstream g("rj.out");
	
	f>>n>>m;
	f.get();
	for(int i=1;i<=n;i++)
	{
			f.getline(x[i],104);
			
			for(int j=0;j<m;j++)
			{
				if(x[i][j]=='R')
				{
					pri=i;
					prj=j;
				}
				else if(x[i][j]=='J')
				{
					pji=i;
					pjj=j;
				}
			}
	}
	
	parcurg(pri,prj,pji,pjj,rom);
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			mat[i][j]=0;
	
	parcurg(pji,pjj,pri,prj,jul);
				
	int min=100000,fi,fj;
	
	for(int i=1;i<=n;i++)
		for(int j=0;j<m;j++)
			if(rom[i][j]==jul[i][j]  && rom[i][j]!=0 && rom[i][j]<min)
			{
				min=rom[i][j];
				fi=i;
				fj=j+1;
			}
			
			g<<min<<" "<<fi<<" "<<fj;
			
			return 0;
}