Cod sursa(job #2071362)

Utilizator x3o2andyandrei x3o2andy Data 20 noiembrie 2017 17:04:13
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.09 kb
#include<fstream>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<limits.h>

#define X x[i]
#define Y y[i]

using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

int n, m;
int M[103][103], R[103][103], J[103][103];

int Rx, Ry, Jx, Jy;

void bordare() {

	int i, j;

	for (i = 0; i < n + 1; i++) {
		M[0][i] = -1;
		M[i][n + 1] = -1;
	}
	for (i = 0; i < m + 1; i++) {
		M[i][0] = -1;
		M[n + 1][i] = -1;
	}
}

void read() {
	int i, j;
	f >> n >> m;

	bordare();
	char x[256];
	f.get();
	for (i = 1; i < n + 1; i++) {
		f.getline(x, 256);
		for (j = 0; j <strlen(x); j++) {
			if (x[j] == 'X')
				M[i][j+1] = -1;
			if (x[j] == 'R') {
				Rx = i; Ry = j+1;
				R[i][j + 1] = -1;
			}
			if (x[j] == 'J') {
				Jx = i; Jy = j+1;
				J[i][j + 1] = -1;
			}
		}
	}
}

void print() {
	int i, j;

	for (i = 1; i < n + 1; i++) {
		cout << "\n";
		for (j = 1; j < m + 1; j++)
			cout << R[i][j] << ' ';
	}		

	cout << "\n \n";

	for (i = 1; i < n + 1; i++) {
		cout << "\n";
		for (j = 1; j < m + 1; j++)
			cout << J[i][j] << ' ';
	}

	cout << "\n \n";

	for (i = 1; i < n + 1; i++) {
		cout << "\n";
		for (j = 1; j < m + 1; j++)
			cout << M[i][j] << ' ';
	}
}

void LeeR() {
	int i, j;
	int x[10300], y[103000];
	R[Rx][Ry] = 1;
	i = 0; j = 0;
	x[0] = Rx; y[0] = Ry; j++;

	while (i < j) {
		if (X == Jx && Y == Jy) {
			break;
		}

		if (M[X+1][Y] == 0 && R[X+1][Y] == 0) {
			x[j] = X + 1;
			y[j] = Y;
			R[X + 1][Y] = R[X][Y] + 1;

			j++;
		}

		if (M[X - 1][Y] == 0 && R[X - 1][Y] == 0) {
			x[j] = X - 1;
			y[j] = Y;
			R[X - 1][Y] = R[X][Y] + 1;

			j++;
		}

		if (M[X][Y + 1] == 0 && R[X][Y + 1] == 0) {
			x[j] = X;
			y[j] = Y + 1;
			R[X][Y + 1] = R[X][Y] + 1;

			j++;
		}

		if (M[X][Y - 1] == 0 && R[X][Y - 1] == 0) {
			x[j] = X;
			y[j] = Y - 1;
			R[X][Y - 1] = R[X][Y] + 1;
			j++;
		}
		//diagonal

		if (M[X + 1][Y + 1] == 0 && R[X + 1][Y + 1] == 0) {
			x[j] = X + 1;
			y[j] = Y + 1;
			R[X + 1][Y + 1] = R[X][Y] + 1;

			j++;
		}

		if (M[X - 1][Y - 1] == 0 && R[X - 1][Y - 1] == 0) {
			x[j] = X - 1;
			y[j] = Y - 1;
			R[X - 1][Y - 1] = R[X][Y] + 1;

			j++;
		}

		if (M[X - 1][Y + 1] == 0 && R[X - 1][Y + 1] == 0) {
			x[j] = X - 1;
			y[j] = Y + 1;
			R[X - 1][Y + 1] = R[X][Y] + 1;

			j++;
		}

		if (M[X + 1][Y - 1] == 0 && R[X + 1][Y - 1] == 0) {
			x[j] = X + 1;
			y[j] = Y - 1;
			R[X + 1][Y - 1] = R[X][Y] + 1;
			j++;
		}	
		i++;
	}
}

void LeeJ() {
	int i, j;
	int x[10300], y[103000];
	J[Jx][Jy] = 1;
	i = 0; j = 0;
	x[0] = Jx; y[0] = Jy; j++;

	while (i < j) {
		if (X == Rx && Y == Ry)
			break;

		if (M[X + 1][Y] == 0 && J[X + 1][Y] == 0) {
			x[j] = X + 1;
			y[j] = Y;
			J[X + 1][Y] = J[X][Y] + 1;

			j++;
		}

		if (M[X - 1][Y] == 0 && J[X - 1][Y] == 0) {
			x[j] = X - 1;
			y[j] = Y;
			J[X - 1][Y] = J[X][Y] + 1;

			j++;
		}

		if (M[X][Y + 1] == 0 && J[X][Y + 1] == 0) {
			x[j] = X;
			y[j] = Y + 1;
			J[X][Y + 1] = J[X][Y] + 1;

			j++;
		}

		if (M[X][Y - 1] == 0 && J[X][Y - 1] == 0) {
			x[j] = X;
			y[j] = Y - 1;
			J[X][Y - 1] = J[X][Y] + 1;
			j++;
		}
		//diagonal

		if (M[X + 1][Y + 1] == 0 && J[X + 1][Y + 1] == 0) {
			x[j] = X + 1;
			y[j] = Y + 1;
			J[X + 1][Y + 1] = J[X][Y] + 1;

			j++;
		}

		if (M[X - 1][Y - 1] == 0 && J[X - 1][Y - 1] == 0) {
			x[j] = X - 1;
			y[j] = Y - 1;
			J[X - 1][Y - 1] = J[X][Y] + 1;

			j++;
		}

		if (M[X - 1][Y + 1] == 0 && J[X - 1][Y + 1] == 0) {
			x[j] = X - 1;
			y[j] = Y + 1;
			J[X - 1][Y + 1] = J[X][Y] + 1;

			j++;
		}

		if (M[X + 1][Y - 1] == 0 && J[X + 1][Y - 1] == 0) {
			x[j] = X + 1;
			y[j] = Y - 1;
			J[X + 1][Y - 1] = J[X][Y] + 1;
			j++;
		}
		i++;
	}
}

void solve() {
	LeeR();
	LeeJ();

	int min1 = INT_MAX;
	int i, j;
	for(i=1;i<n+1;i++)
		for (j = 1; j < m + 1; j++) {
			if (R[i][j] == J[i][j] && R[i][j] != 0) {
				g << R[i][j] << ' ' << i << ' ' << j;
				return;
			}
		}

	cout << min1;
}

int main()
{
	read();
	solve();
	//print();
    return 0;
}