Cod sursa(job #634322)

Utilizator ionutmodoModoranu Ionut-Vlad ionutmodo Data 15 noiembrie 2011 22:17:04
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<fstream>
#include<cstring>
#include<iostream>
using namespace std;

struct coord
{
	short x,y;
};
coord q[200010];

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

int R[110][110],J[110][110];
int L,C,xR,yR,xJ,yJ;

void ReadData()
{
	ifstream fin("rj.in");
	fin>>L>>C;
	fin.get();
	int i,j;
	char s[110];
	for(i=1; i<=L; i++)
	{
		fin.getline(s,110);
		for(j=0; j<C; j++)
			if(s[j]==' ')
				R[i][j+1] = 0;
			else if(s[j]=='X')
				R[i][j+1] = 1;
			else if(s[j]=='R')
				{
					xR = i;
					yR = j+1;
				}
				else
					if(s[j]=='J')
					{
						xJ = i;
						yJ = j+1;
					}
	}
	fin.close();
	
	for(i=1; i<=L; i++)
		for(j=1; j<=C; j++)
			J[i][j] = R[i][j];
	
	R[xR][yR] = 2;
	R[xJ][yJ] = 2;
	
	cout<<xR<<" "<<yR<<"\n";
	cout<<xJ<<" "<<yJ<<"\n";
	
}

void Bordare()
{
	int i,n,m;
	n = L + 1;
	m = C + 1;
	for(i=0; i<=n;i++)
		R[i][0] = J[i][0] = R[i][m] = J[i][m] = -1;
	for(i=0; i<=m; i++)
		R[0][i] = J[0][i] = R[n][i] = J[n][i] = -1;
}

void Romeo()
{
	int i,j,x,y,k,pr,ul;
	pr = ul = 0;
	
	q[0].x = xR;
	q[0].y = yR;
	
	while(pr<=ul)
	{
		x = q[pr].x;
		y = q[pr].y;
		pr++;
		for(k=0; k<8; k++)
		{
			i = x + dx[k];
			j = y + dy[k];
			if(R[i][j] == 0)
			{
				ul++;
				q[ul].x = i;
				q[ul].y = j;
				R[i][j] = R[x][y] + 1;
			}
		}
	}
}
void Julieta()
{
	int i,j,x,y,k,pr,ul;
	pr = ul = 0;
	
	q[0].x = xJ;
	q[0].y = yJ;
	
	while(pr<=ul)
	{
		x = q[pr].x;
		y = q[pr].y;
		pr++;
		for(k=0; k<8; k++)
		{
			i = x + dx[k];
			j = y + dy[k];
			if(J[i][j] == 0)
			{
				ul++;
				q[ul].x = i;
				q[ul].y = j;
				J[i][j] = J[x][y] + 1;
			}
		}
	}
}

void Scriere()
{
	int i,j,lin,col,timp = 1000000;
	lin = col = 0;
	
	for(i=1; i<=L; i++)
		for(j=1; j<=C; j++)
		{
			if(R[i][j] == J[i][j] && R[i][j] != 1)
				if(R[i][j] - 1 < timp)
				{
					lin = i;
					col = j;
					timp = R[i][j] - 1;
				}
		}
	
	ofstream fout("rj.out");
	fout<<timp<<" "<<lin<<" "<<col<<"\n";
	fout.close();
}

int main ()
{
	ReadData();
	Bordare();
	/*
	ofstream fout("rj.out");
	int i,j;
	for(i=1; i<=L; i++)
	{
		for(j=1; j<=C; j++)
			fout<<R[i][j]<<" ";
		fout<<"\n";
	}
	fout.close();
	*/
	Romeo();
	Julieta();
	
	Scriere();
	
	return 0;
}