Cod sursa(job #555135)

Utilizator theodora_maneaManea Theodora Maria theodora_manea Data 15 martie 2011 12:04:14
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#include <string.h>

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

int i,n,m,j,imin,jmin,i1,j1,i2,j2,min,nr;
int a[101][101],b[101][101];
char s[101];
int q[10001][2];

void lee1() {
	int x,y,xx,yy,i,st,dr;
	q[1][0]=i1; q[1][1]=j1;
	st=1; dr=1;
	while (st<=dr) {
		x=q[st][0];
		y=q[st][1];
		for (i=0; i<8; i++) {
			xx=x+dx[i];
			yy=y+dy[i];
			if (xx>=1 && xx<=n && yy>=1 && yy<=m) 
				if (a[xx][yy]==0) {
					if (a[x][y]==-1) a[xx][yy]=a[x][y]+2;
					else a[xx][yy]=a[x][y]+1;
					dr++;
					q[dr][0]=xx;
					q[dr][1]=yy;
				}
		}
		st++;
	}
}

void lee2() {
	int x,y,xx,yy,i,st,dr;
	q[1][0]=i2; q[1][1]=j2;
	st=1; dr=1;
	while (st<=dr) {
		x=q[st][0];
		y=q[st][1];
		for (i=0; i<8; i++) {
			xx=x+dx[i];
			yy=y+dy[i];
			if (xx>=1 && xx<=n && yy>=1 && yy<=m) 
				if (b[xx][yy]==0) {
					if (b[x][y]==-1) b[xx][yy]=b[x][y]+2;
					else b[xx][yy]=b[x][y]+1;
					dr++;
					q[dr][0]=xx;
					q[dr][1]=yy;
				}
		}
		st++;
	}
}
					

int main () {
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d%d\n",&n,&m);
	for (i=1; i<=n; i++) {
		fgets(s,110,stdin);
		for (j=0; j<m; j++) 
			if (s[j]==' ') a[i][j+1]=0;
		else 
			if (s[j]=='X') a[i][j+1]=-1;
		else
			if (s[j]=='J') {
				a[i][j+1]=-1;
				i2=i;
				j2=j+1;
			}
			else
				if (s[j]=='R') {
					a[i][j+1]=-1;
					i1=i;
					j1=j+1;
				}
	}
	
	for (i=1; i<=n; i++)
		for (j=1; j<=m; j++) b[i][j]=a[i][j];
	lee1();
	lee2();
	
	min=n*m+1;
	for (i=1; i<=n; i++) 
		for (j=1; j<m; j++)
			if (a[i][j]==b[i][j] && a[i][j]>=1)
				if (min>a[i][j]) {
					min=a[i][j];
					imin=i;
					jmin=j;
				}
	printf("%d %d %d\n",min+1,imin,jmin);
	return 0;
}