Cod sursa(job #136428)

Utilizator tudalexTudorica Constantin Alexandru tudalex Data 15 februarie 2008 15:52:01
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

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

FILE *f;
char t;
char a[n_max][n_max],
     v[n_max][n_max];

int  b[2][n_max][n_max];

int i, j, n, m, l, p[2][2];
char s[n_max];

void bf(int c)
{
	int stiv[n_max*n_max][2];
	int left = 0, right = 0;
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= m; ++ j)
			v[i][j] = 0;


	stiv[++right][0] = p[c][0];
	stiv[right][1] = p[c][1];
	v[p[c][0]][p[c][1]] = 1;
	b[c][p[c][0]][p[c][1]] = 1;
	while (left <right)
	{
		++left;
		int x = stiv[left][0];
		int y = stiv[left][1];

		for (int i = 0; i < 8; ++ i)
		if ( a[x+dx[i]][y+dy[i]] == 1 && !v[x+dx[i]][y+dy[i]])
		{
			v[x+dx[i]][y+dy[i]] = 1;
			b[c][x+dx[i]][y+dy[i]] = b[c][x][y] + 1;
			stiv[++right][0] = x + dx[i];
			stiv[right][1] = y + dy[i];
		}
	}

}

int main()
{
	f=fopen("rj.in","r");
	freopen("rj.out","w",stdout);
	fscanf(f,"%d %d\n", &n, &m);
	//Allocam memorie
 /*   for (i = 1; i <= n_max; ++ i)
	{
	       b[0][i] = (int *)malloc(sizeof(int)*n_max);
	       b[1][i] = (int *)malloc(sizeof(int)*n_max);
	}*/
	for (i = 1; i <= n; ++ i)
	{
		for (j = 0; j < m; ++ j)
		{

			fscanf(f,"%c",&t);
			if (t == 'R')
			{
				p[0][0] = i;
				p[0][1] = j+1;
			}
			else
			if (t == 'J')
			{
				p[1][0] = i;
				p[1][1] = j+1;
			}
			else
			if (t == ' ')
			{
				a[i][j+1] = 1;
			}
		}
		fscanf(f," \n");
	}
	bf(0);
	bf(1);
       /*	for (i = 1; i <= n; ++ i)
	{
		for(j = 1; j <= m; ++ j)
		printf("%d ", b[0][i][j]);
		printf("\n");
	}*/
	for (i = 1; i <= n; ++ i)
		for (j = 1; j <= m; ++ j)
		{
			if ( a[i][j] == 1 && b[0][i][j] !=0 && b[0][i][j] == b[1][i][j])
			{
				printf("%d %d %d\n", b[0][i][j], i, j);
				return 0;
			}
		}
	return 0;
}