Cod sursa(job #747790)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 11 mai 2012 20:45:48
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include<stdio.h>
#include<string.h>
#define NMAX 104
#define QMAX 100000
int A[ NMAX ][ NMAX ], B[ NMAX ][ NMAX ], v[ QMAX ][2], n, m, i, j, x1, y1, x2, y2, x, y, res = QMAX;
char S[ NMAX ];
void read()
{
	int len;
	FILE *f = fopen("rj.in", "r");
	fscanf(f, "%d %d", &n, &m);
	fgets(S, 3, f);
	for(i = 1; i <= n; i++)
	{
		fgets(S, 102, f);
		if( S[ strlen(S) - 1 ] == '\n')
			S[ strlen(S) - 1 ] = '\0';
		len = strlen(S);
		for(j = 0; j < len; j++)
			if(S[j] == 'X')
				A[i][j+1] = B[i][j+1] = -1;
			else if(S[j] == 'R')
				x1 = i, y1 = j + 1;
			else if(S[j] == 'J')
				x2 = i, y2 = j + 1;
	}
	fclose(f);
}
void initialization()
{
	for(i = 0; i <= n + 1; i++)
		A[i][0] = A[i][m+1] = B[i][0] = B[i][m+1] = -1;
	for(j = 1; j <= m + 1; j++)
		A[0][j] = A[n+1][j] = B[0][j] = B[n+1][j] = -1;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			if(A[i][j] != -1)
				A[i][j] = B[i][j] = QMAX;
}
void solve()
{
	int k, q;
	initialization();
	k = 1, v[1][0] = x1, v[1][1] = y1;
	A[x1][y1] = 1;
	for(q = 1; q <= k; q++)
	{
		i = v[q][0], j = v[q][1];
		// N:
		if(A[i][j] + 1 < A[i-1][j])
			A[i-1][j] = A[i][j] + 1, k++, v[k][0] = i-1, v[k][1] = j;
		// NE:
		if(A[i][j] + 1 < A[i-1][j+1])
			A[i-1][j+1] = A[i][j] + 1, k++, v[k][0] = i-1, v[k][1] = j+1;
		// E:
		if(A[i][j] + 1 < A[i][j+1])
			A[i][j+1] = A[i][j] + 1, k++, v[k][0] = i, v[k][1] = j+1;
		// SE
		if(A[i][j] + 1 < A[i+1][j+1])
			A[i+1][j+1] = A[i][j] + 1, k++, v[k][0] = i+1, v[k][1] = j+1;
		// S
		if(A[i][j] + 1 < A[i+1][j])
			A[i+1][j] = A[i][j] + 1, k++, v[k][0] = i+1, v[k][1] = j;
		// SV
		if(A[i][j] + 1 < A[i+1][j-1])
			A[i+1][j-1] = A[i][j] + 1, k++, v[k][0] = i+1, v[k][1] = j-1;
		// V
		if(A[i][j] + 1 < A[i][j-1])
			A[i][j-1] = A[i][j] + 1, k++, v[k][0] = i, v[k][1] = j-1;
		// NV
		if(A[i][j] + 1 < A[i-1][j-1])
			A[i-1][j-1] = A[i][j] + 1, k++, v[k][0] = i-1, v[k][1] = j-1;
	}

	k = 1, v[1][0] = x2, v[1][1] = y2;
	B[x2][y2] = 1;
	for(q = 1; q <= k; q++)
	{
		i = v[q][0], j = v[q][1];
		// N:
		if(B[i][j] + 1 < B[i-1][j])
			B[i-1][j] = B[i][j] + 1, k++, v[k][0] = i-1, v[k][1] = j;
		// NE:
		if(B[i][j] + 1 < B[i-1][j+1])
			B[i-1][j+1] = B[i][j] + 1, k++, v[k][0] = i-1, v[k][1] = j+1;
		// E:
		if(B[i][j] + 1 < B[i][j+1])
			B[i][j+1] = B[i][j] + 1, k++, v[k][0] = i, v[k][1] = j+1;
		// SE
		if(B[i][j] + 1 < B[i+1][j+1])
			B[i+1][j+1] = B[i][j] + 1, k++, v[k][0] = i+1, v[k][1] = j+1;
		// S
		if(B[i][j] + 1 < B[i+1][j])
			B[i+1][j] = B[i][j] + 1, k++, v[k][0] = i+1, v[k][1] = j;
		// SV
		if(B[i][j] + 1 < B[i+1][j-1])
			B[i+1][j-1] = B[i][j] + 1, k++, v[k][0] = i+1, v[k][1] = j-1;
		// V
		if(B[i][j] + 1 < B[i][j-1])
			B[i][j-1] = B[i][j] + 1, k++, v[k][0] = i, v[k][1] = j-1;
		// NV
		if(B[i][j] + 1 < B[i-1][j-1])
			B[i-1][j-1] = B[i][j] + 1, k++, v[k][0] = i-1, v[k][1] = j-1;
	}
	
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			if(A[i][j] != -1 && A[i][j] != QMAX && B[i][j] != -1 && B[i][j] != QMAX && A[i][j]  < res && A[i][j] == B[i][j])
				res = A[i][j], x = i, y = j;
}
void write()
{
	FILE *g = fopen("rj.out", "w");
	fprintf(g, "%d %d %d\n", res, x, y);
	fclose(g);
}
int main()
{
	read();
	solve();
	write();
	return 0;
}