Cod sursa(job #83892)

Utilizator andrei.12Andrei Parvu andrei.12 Data 12 septembrie 2007 13:07:36
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<stdio.h>
#include<stdlib.h>
const int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
const int dy[] = {-1, 0, 1, -1, 0, 1, 1, -1};
int i, j, a[105][105], d[105][105], p, t, x, y, xx, yy, n, m, dmin, s, nr;
char c;
struct ches{
	int a, b, l;
};
ches q[10000], w[10000];
struct get{
	int x, y;
};
get sol[10000];
int comp(const void*a, const void*b){
	get x = *(get*)a, y = *(get*)b;
	if (x.x < y.x) return -1;
	if (x.x > y.x) return 1;
	if (x.y < y.y) return -1;
	if (x.y > y.y) return 1;
	return 0;
}
int main()
{
	freopen("rj.in","r",stdin);
	freopen("rj.out","w",stdout);
	scanf("%d%d", &n, &m);
	scanf("%c", &c);
	for (i=1; i<=n; i++){
		for (j=1; j<=m; j++){
			c = fgetc(stdin);
			if (c == 'X')
				a[i][j] = 2;
			if (c == 'R'){
				a[i][j] = 1;
				q[1].a = i;
				q[1].b = j;
			}
			if (c == 'J'){
				a[i][j] = 0;
				w[1].a = i;
				w[1].b = j;
			}
		}
		scanf("%c%c", &c, &c);
	}
	q[1].l = 1;
	p = 0;
	t = 1;
	while (p < t){
		p ++;
		x = q[p].a;
		y = q[p].b;
		for (i=0; i<8; i++){
			xx = x+dx[i];
			yy = y+dy[i];
			if (!a[xx][yy] && xx && xx <=n && yy && yy <= m){
				d[xx][yy] = q[p].l+1;
				a[xx][yy] = 1;
				q[++t].a = xx;
				q[t].b = yy;
				q[t].l = d[xx][yy];
			}
		}
	}
	a[w[1].a][w[1].b] = 2;
	w[1].l = 1;
	p = 0;
	t = 1;
	s = 0;
	while(p < t){
		p ++;
		x = w[p].a;
		y = w[p].b;
		for (i=0; i<8; i++){
			xx = x+dx[i];
			yy = y+dy[i];
			if (a[xx][yy] == 1 && xx && x <= n && yy && yy <= m){
				a[xx][yy] = 2;
				w[++t].a = xx;
				w[t].b = yy;
				w[t].l = w[p].l+1;
				if (!s){
					if (d[xx][yy] == w[t].l){
						dmin = d[xx][yy];
						sol[++nr].x = xx;
						sol[nr].y = yy;
						s = 1;
					}
				}
				else
					if (d[xx][yy] == w[t].l && w[t].l == dmin){
						sol[++nr].x = xx;
						sol[nr].y = yy;
					}
			}
		}
	}
	qsort(sol, nr+1, sizeof(sol[0]), comp);
	printf("%d %d %d\n", dmin, sol[1].x, sol[1].y);
	fclose(stdin);
	fclose(stdout);
	return 0;
}