Cod sursa(job #704140)

Utilizator @LynTirla Alin @Lyn Data 2 martie 2012 16:32:50
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<cstdio>
//perle 2004
//spirala 2003
using namespace std;
char b[105];
vector <int> coada,coada1;
short a[105][105];
int romeo[105][105],julieta[105][105];
bool fol[105][105],fol1[105][105];
short x[10]={0,0,1,-1,1,1,-1,-1},y[10]={1,-1,0,0,1,-1,1,-1};
int n,m;
int xul,yul;
int drummin=9999999;
void cauta()
{
	int xnou,ynou;
	for(int i=0;i<coada.size();i+=2)
	{
		for(int d=0;d<=7;++d)
		{
			xnou=coada[i]+x[d];
			ynou=coada[i+1]+y[d];
			if((xnou>=1)&&(ynou>=1)&&(ynou<=m)&&(xnou<=n)&&(!a[xnou][ynou]))
			{
				if(!fol[xnou][ynou])
				{
					coada.push_back(xnou);
					coada.push_back(ynou);
					fol[xnou][ynou]=1;
				}
				else
				{
					if(romeo[xnou][ynou])
					{
						if(!romeo[coada[i]][coada[i+1]])
						{
							romeo[coada[i]][coada[i+1]]=romeo[xnou][ynou]+1;
						}
						else romeo[coada[i]][coada[i+1]]=min(romeo[coada[i]][coada[i+1]],romeo[xnou][ynou]+1);
					}
				}
			}
		}
	}
}
void cauta1()
{
	int xnou,ynou;
	for(int i=0;i<coada1.size();i+=2)
	{
		for(int d=0;d<=7;++d)
		{
			xnou=coada1[i]+x[d];
			ynou=coada1[i+1]+y[d];
			if((xnou>=1)&&(ynou>=1)&&(ynou<=m)&&(xnou<=n)&&(!a[xnou][ynou]))
			{
				if(!fol1[xnou][ynou])
				{
					coada1.push_back(xnou);
					coada1.push_back(ynou);
					fol1[xnou][ynou]=1;
				}
				else
				{
					if(julieta[xnou][ynou])
					{
						if(!julieta[coada1[i]][coada1[i+1]])
						{
							julieta[coada1[i]][coada1[i+1]]=julieta[xnou][ynou]+1;
						}
						else julieta[coada1[i]][coada1[i+1]]=min(julieta[coada1[i]][coada1[i+1]],julieta[xnou][ynou]+1);
					}
				}
			}
		}
		if(romeo[coada1[i]][coada1[i+1]]==julieta[coada1[i]][coada1[i+1]])
		{
			if(drummin>romeo[coada1[i]][coada1[i+1]])
				{
					drummin=romeo[coada1[i]][coada1[i+1]];
					xul=coada1[i];
					yul=coada1[i+1];
				}
			else if(drummin==romeo[coada1[i]][coada1[i+1]])
			{
				if(xul>coada1[i])
				{
					xul=coada1[i];
					yul=coada1[i+1];
				}
				else if(xul==coada1[i])
				{
					if(yul>coada1[i])
					{
						xul=coada1[i];
						yul=coada1[i+1];
					}
				}
			}
		}
	}
}
int main()
{
	ifstream f1("rj.in");
	ofstream f2("rj.out");
	f1>>n>>m;
	for(int i=0;i<=n;++i)
	{
		f1.getline(b,101);
		for(int d=0;d<strlen(b);++d)
		{
			
			if(b[d]=='X') 
				{
					a[i][d+1]=1;
				}
			else if(b[d]=='R') 
				{
					coada.push_back(i);
					coada.push_back(d+1);
					fol[i][d+1]=1;
					romeo[i][d+1]=1;
				}
			else if(b[d]=='J')
				{
					coada1.push_back(i);
					coada1.push_back(d+1);
					fol1[i][d+1]=1;
					julieta[i][d+1]=1;
				}
		}
	}
	
	cauta();
	cauta1();
	f2<<drummin<<" "<<xul<<" "<<yul<<" ";
	//for(int i=1;i<=n;++i)
	//{
	//	for(int d=1;d<=m;++d)
	//	{
	//		f2<<romeo[i][d]<<" ";
	//	}
	//	f2<<'\n';
	//}
	//f2<<'\n';
	//f2<<'\n';
	//for(int i=1;i<=n;++i)
	//{
	//	for(int d=1;d<=m;++d)
//		{
	//		f2<<julieta[i][d]<<" ";
		//}
//		f2<<'\n';
//	}
//		
	
	return 0;
}