Cod sursa(job #654945)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 31 decembrie 2011 13:26:34
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<iostream>
#include<fstream>
#include<bitset>
#include<string.h>
using namespace std;
struct coada {
	unsigned char x,y;
};
coada c[10001],aa,b,rr,jj;
char a[102][102];
unsigned short r[102][102],julieta[102][102];
bitset <102> d[102];
int dx[]={0,-1,-1,0,1,1,1,0,-1};
int dy[]={0,0,1,1,1,0,-1,-1,-1};
void parcurgere(coada rr)
{
	int i,st,dr;
	d[rr.x][rr.y]=1;
	r[rr.x][rr.y]=1;
	st=1;
	dr=1;
	c[st]=rr;
	while(st<=dr) {
		aa=c[st];
		st++;
		for(i=1;i<=8;i++) {
			b.x=aa.x+dx[i];
			b.y=aa.y+dy[i];
			if((d[b.x][b.y]==0)&&(a[b.x][b.y]==4)) {
				d[b.x][b.y]=1;
				r[b.x][b.y]=r[aa.x][aa.y]+1;
				dr++;
				c[dr]=b;
			}
		}
	}
}
int main ()
{
	int i,j,n,m,k,l,min;
	char cc[102];
	ifstream f("rj.in");
	ofstream g("rj.out");
	f>>n>>m;
	f.get();
	for(i=1;i<=n;i++) {
		f.get(cc,101);
		f.get();
		l=strlen(cc)-1;
		for(j=0;j<=l;j++) {
			if(cc[j]==' ')
 				a[i][j+1]=4;
			else if(cc[j]=='X')
				a[i][j+1]=3;
			else if(cc[j]=='R') {
				a[i][j+1]=1;
				rr.x=i;
				rr.y=j+1;
			}
			else {
				a[i][j+1]=2;
				jj.x=i;
				jj.y=j+1;
			}
		}
		for(k=j+1;k<=m;k++)
			a[i][k]=0;
	}
	f.close();
	parcurgere(jj);
	for(i=1;i<=n;i++) 
		for(j=1;j<=m;j++) {
			julieta[i][j]=r[i][j];
			r[i][j]=0;
			d[i][j]=0;
		}
	parcurgere(rr);
	min=100000;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			if((r[i][j]==julieta[i][j])&&(r[i][j]>0)&&(r[i][j]<min)) {
				min=r[i][j];
				rr.x=i;
				rr.y=j;
			}
	g<<min<<" "<<int(rr.x)<<" "<<int(rr.y);
	return 0;
}