Cod sursa(job #474633)

Utilizator darrenRares Buhai darren Data 4 august 2010 14:41:02
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <cstring>
#include <fstream>
#include <queue>

using namespace std;

const int d1[] = {0, 1, 0, -1, 1, 1, -1, -1},
          d2[] = {1, 0, -1, 0, 1, -1, 1, -1};

#define x first
#define y second

pair<int, int> p1, p2;
int n, m, a[101][101];
queue<pair<int, int> > q1, q2;
int m1[101][101], m2[101][101];
bool b1[101][101], b2[101][101];

int main()
{
	ifstream fin("rj.in");
	ofstream fout("rj.out");
	fin >> n >> m;

	char auxs[120];

	fin.getline(auxs, 120);

	for (int i = 0; i < n; ++i)
	{
		memset(auxs, 0, sizeof(auxs));
		fin.getline(auxs, 120);
		for (int j = 0; j < m; ++j)
			switch(auxs[j])
			{
			case 'J':
				p1.x = i, p1.y = j;
				break;
			case 'R':
				p2.x = i, p2.y = j;
				break;
			case 'X':
				a[i][j] = 1;
				break;
			}
	}
	memset(m1, -1, sizeof(m1));
	memset(m2, -1, sizeof(m2));

	//J
	q1.push(p1);
	m1[p1.x][p1.y] = 0;
	b1[p1.x][p1.y] = true;
	while (!q1.empty())
	{
		pair<int, int> aux = q1.back();
		q1.pop();
		for (int k = 0; k < 8; ++k)
		{
			pair<int, int> now = aux;
			now.x += d1[k];
			now.y += d2[k];
			if (now.x >= 0 && now.y >= 0 && now.x < n && now.y < m && !b1[now.x][now.y] && !a[now.x][now.y])
			{
				m1[now.x][now.y] = m1[aux.x][aux.y] + 1;
				b1[now.x][now.y] = true;
				q1.push(make_pair(now.x, now.y));
			}
		}
	}
	//R
	q2.push(p2);
	m2[p2.x][p2.y] = 0;
	b2[p2.x][p2.y] = true;
	while (!q2.empty())
	{
		pair<int, int> aux = q2.back();
		q2.pop();
		for (int k = 0; k < 8; ++k)
		{
			pair<int, int> now = aux;
			now.x += d1[k];
			now.y += d2[k];
			if (now.x >= 0 && now.y >= 0 && now.x < n && now.y < m && !b2[now.x][now.y] && !a[now.x][now.y])
			{
				m2[now.x][now.y] = m2[aux.x][aux.y] + 1;
				b2[now.x][now.y] = true;
				q2.push(make_pair(now.x, now.y));
			}
		}
	}

	int mn = 100000000, p1, p2;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			if (m1[i][j] == m2[i][j] && m1[i][j] < mn && m1[i][j] != -1)
			{
				p1 = i, p2 = j,
				mn = m1[i][j];
			}
	fout << mn + 1 << ' ' << p1 + 1 << ' ' << p2 + 1;
}