Cod sursa(job #1555870)

Utilizator SilviuIIon Silviu SilviuI Data 23 decembrie 2015 17:40:50
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <stdio.h>
#include <queue>
#define nmax 110
#define mp make_pair
using namespace std;

int n,m,x,y,xx,yy;
int d1[nmax][nmax],d2[nmax][nmax];
queue < pair<int,int> > que;
char s[nmax][2*nmax];

bool ok(int x,int y) { return (x>0 && y>0 && x<=n && y<=m); }

int main() {
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d %d ",&n,&m);
	for (int i=1;i<=n;i++) fgets(s[i]+1,200,stdin);
	
	for (int i=1;i<=n;i++)  
	   for (int j=1;j<=m;j++)
	       if (s[i][j]=='R') x=i,y=j; else
	          if (s[i][j]=='J') xx=i,yy=j;
	
	que.push(mp(x,y)); d1[x][y]=1;
	while (!que.empty()) {
		int x=que.front().first,y=que.front().second; que.pop();
		if (d1[x+1][y]==0 && s[x+1][y]==' ' && ok(x+1,y)) {
			d1[x+1][y]=d1[x][y]+1; que.push(mp(x+1,y));
		}	
		if (d1[x][y+1]==0 && s[x][y+1]==' ' && ok(x,y+1)) {
			d1[x][y+1]=d1[x][y]+1; que.push(mp(x,y+1));
		}
		if (d1[x-1][y]==0 && s[x-1][y]==' ' && ok(x-1,y)) {
			d1[x-1][y]=d1[x][y]+1; que.push(mp(x-1,y));
		}
		if (d1[x][y-1]==0 && s[x][y-1]==' ' && ok(x,y-1)) {
			d1[x][y-1]=d1[x][y]+1; que.push(mp(x,y-1));
		}
		if (d1[x+1][y+1]==0 && s[x+1][y+1]==' ' && ok(x+1,y+1)) {
			d1[x+1][y+1]=d1[x][y]+1; que.push(mp(x+1,y+1));
		}
		if (d1[x+1][y-1]==0 && s[x+1][y-1]==' ' && ok(x+1,y-1)) {
			d1[x+1][y-1]=d1[x][y]+1; que.push(mp(x+1,y-1));
		}
		if (d1[x-1][y+1]==0 && s[x-1][y+1]==' ' && ok(x-1,y+1)) {
			d1[x-1][y+1]=d1[x][y]+1; que.push(mp(x-1,y+1));
		}
		if (d1[x-1][y-1]==0 && s[x-1][y-1]==' ' && ok(x-1,y-1)) {
			d1[x-1][y-1]=d1[x][y]+1; que.push(mp(x-1,y-1));
		}
	}
	
	que.push(mp(xx,yy)); d2[xx][yy]=1;
		while (!que.empty()) {
		int x=que.front().first,y=que.front().second; que.pop();
		if (d2[x+1][y]==0 && s[x+1][y]==' ' && ok(x+1,y)) {
			d2[x+1][y]=d2[x][y]+1; que.push(mp(x+1,y));
		}	
		if (d2[x][y+1]==0 && s[x][y+1]==' ' && ok(x,y+1)) {
			d2[x][y+1]=d2[x][y]+1; que.push(mp(x,y+1));
		}
		if (d2[x-1][y]==0 && s[x-1][y]==' ' && ok(x-1,y)) {
			d2[x-1][y]=d2[x][y]+1; que.push(mp(x-1,y));
		}
		if (d2[x][y-1]==0 && s[x][y-1]==' ' && ok(x,y-1)) {
			d2[x][y-1]=d2[x][y]+1; que.push(mp(x,y-1));
		}
		if (d2[x+1][y+1]==0 && s[x+1][y+1]==' ' && ok(x+1,y+1)) {
			d2[x+1][y+1]=d2[x][y]+1; que.push(mp(x+1,y+1));
		}
		if (d2[x+1][y-1]==0 && s[x+1][y-1]==' ' && ok(x+1,y-1)) {
			d2[x+1][y-1]=d2[x][y]+1; que.push(mp(x+1,y-1));
		}
		if (d2[x-1][y+1]==0 && s[x-1][y+1]==' ' && ok(x-1,y+1)) {
			d2[x-1][y+1]=d2[x][y]+1; que.push(mp(x-1,y+1));
		}
		if (d2[x-1][y-1]==0 && s[x-1][y-1]==' ' && ok(x-1,y-1)) {
			d2[x-1][y-1]=d2[x][y]+1; que.push(mp(x-1,y-1));
		}
	}
	
	int tmin=0x3f3f3f3f;
	for (int i=1;i<=n;i++)
	    for (int j=1;j<=m;j++)
	        if (d1[i][j]>0 && d1[i][j]==d2[i][j] && d1[i][j]<tmin) {
	        	tmin=d1[i][j]; x=i; y=j;
			}
	
	printf("%d %d %d",tmin,x,y);
	return 0;
}