Pagini recente » Cod sursa (job #1437306) | Cod sursa (job #1978631) | Cod sursa (job #285423) | Cod sursa (job #1843380) | Cod sursa (job #474633)
Cod sursa(job #474633)
#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;
}