Cod sursa(job #888610)

Utilizator StickmanLazar Alexandru Stickman Data 24 februarie 2013 11:49:06
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
#include <string>
#include <iostream>

using namespace std;

ifstream mama("rj.in");
ofstream tata("rj.out");

const short int dx[]={0,-1,0,1,-1,1,-1,1};
const short int dy[]={1,0,-1,0,-1,-1,1,1};

short int x,r[100][100],j[100][100],top,n,m,cxr[100*100],cyr[100*100],cxj[100*100],cyj[100*100];

int buner(short int x, short int y)
{
	if(x>=0 && y>=0 && x<n && y<m && r[x][y]==0) return 1;
			return 0;
}

int bunej(short int x, short int y)
{
	if(x>=0 && y>=0 && x<n && y<m && j[x][y]==0) return 1;
			return 0;
}

int bfsr()
{
	short int i,k,x,y;
	for(i=0;i<top;i++)
		{
			x=cxr[i];
			y=cyr[i];
			for(k=0;k<8;k++)
				{
					if(buner(x+dx[k],y+dy[k])==1)
						{
							cxr[top]=x+dx[k];
							cyr[top]=y+dy[k];
							top++;
							r[x+dx[k]][y+dy[k]]=r[x][y]+1;
						}
				}
		}
}
void bfsj()
{
	short int i,k,x,y;
	for(i=0;i<top;i++)
		{
			x=cxj[i];
			y=cyj[i];
			for(k=0;k<8;k++)
				{
					if(bunej(x+dx[k],y+dy[k])==1)
						{
							cxj[top]=x+dx[k];
							cyj[top]=y+dy[k];
							top++;
							j[x+dx[k]][y+dy[k]]=j[x][y]+1;
						}
				}
		}
}

int main()
{
	short int i,k,x1,x2,y1,y2,min=15000,cc,ccc;
	string x;
	mama>>n>>m;
	getline(mama,x);
	for(i=0;i<n;i++)
	{
		getline(mama,x);
		for(k=0;k<m;k++)
		{
			if(x[k]=='X') {r[i][k]=-1; j[i][k]=-1;}
				else
			if(x[k]=='R') {r[i][k]=1; x1=i; y1=k;}
				else
			if(x[k]=='J') {j[i][k]=1; x2=i; y2=k;}

		}
	}
	cxr[0]=x1; cyr[0]=y1;
	top=1;

	bfsr();


	cxj[0]=x2; cyj[0]=y2;
	top=1;

	bfsj();

	for(i=0;i<n;i++)
		for(k=0;k<m;k++)
			 if(r[i][k]==j[i][k] && r[i][k]<min && r[i][k]>0) {x1=i+1; x2=k+1; min=r[i][k];}

	tata<<min<<" "<<x1<<" "<<x2;

	mama.close();
	tata.close();
	return 0;
}