Cod sursa(job #269942)

Utilizator mihnea_andreiMihnea Andrei mihnea_andrei Data 3 martie 2009 16:41:37
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include<iostream>
#include<fstream>
#include<stdio.h>
#define N 102
#define M 402

using namespace std;

int r[N][N],j[N][N],n,m,ro[2],ju[2];
char a[N];
const int d0[8]={1,1,1,-1,-1,-1,0,0};
const int d1[8]={-1,0,1,-1,0,1,-1,1};
ifstream in("rj.in");
ofstream out ("rj.out");

void citire ()
{
	char c;
	int i,k;
	in>>n>>m>>ws;
	//freopen("rj");
	for(i=1;i<=n;i++)
	{
		in.getline (a,N);
		for(k=0;a[k];k++)
		{
			if(a[k]=='X')
			{
				r[i][k+1]=-1;
				j[i][k+1]=-1;
			}
			if(a[k]==' ')
			{
				r[i][k+1]=0;
				j[i][k+1]=0;
			}
			if(a[k]=='R')
			{
				r[i][k+1]=1;
				ro[0]=i;
				ro[1]=k+1;
			}
			if(a[k]=='J')
			{
				j[i][k+1]=1;
				ju[0]=i;
				ju[1]=k+1;
			}
		}
	}
	for(i=0;i<=n+1;++i)
		r[i][0]=j[i][0]=r[i][m+1]=j[i][m+1]=-1;
	for(i=0;i<=m+1;++i)
		r[0][i]=j[0][i]=r[n+1][i]=j[n+1][i]=-1;
}

void scrie (int r[N][N])
{
	int i,k;
	for (i=1;i<=n;i++)
	{
		for(k=1;k<=m;k++)
			cout<<r[i][k]<<"\t";
		cout<<endl;
	}
	cout<<endl;
}

inline void inc(int &x)
{
	x=(x==M-1 ? 0 : x+1);
}
void bfs (int v[N][N], int x0[2])
{
	int p=0,u=0,i,x[2],y[2],coada[M][2];
	coada[u][0]=x0[0];
	coada[u][1]=x0[1];
	inc(u);
	while(p!=u)
	{
		x[0]=coada[p][0];
		x[1]=coada[p][1];
		inc(p);
		for(i=0;i<8;i++)
		{
			y[0]=x[0]+d0[i];
			y[1]=x[1]+d1[i];
			if(v[y[0]][y[1]]==0)
			{
				coada[u][0]=y[0];
				coada[u][1]=y[1];
				inc(u);
				v[y[0]][y[1]]=1+v[x[0]][x[1]];
			}
		}
	}
}

int main ()
{
	int i,k,w,q,min=32767;
	citire (); 
	//cout<<n<<" "<<m;
	//scrie (j);
	//return 0;
	//cout<<ro[0]<<" "<<ro[1]<<endl;
	//cout<<ju[0]<<" "<<ju[1]<<endl;
	//scrie(r);
	//scrie(j);
	bfs(r,ro);
	bfs(j,ju);
	//scrie(r);
	//return 0;
	//scrie(j);
	
	for(i=1;i<=n;i++)
		for(k=1;k<=m;k++)
			if(r[i][k]==j[i][k] && r[i][k]>=1)
			{
				//printf("avem egalitate pe poz (%d,%d)\n",i,k);
				if(min>r[i][k])
				{
					min=r[i][k];
					w=i;
					q=k;
				}
			}
	
	out<<min<<" "<<w<<" "<<q<<" "<<endl;
	//scrie();
	in.close ();
	out.close ();
	return 0;
}