Pagini recente » Cod sursa (job #2126830) | Cod sursa (job #1576697) | Cod sursa (job #125133) | Cod sursa (job #150681) | Cod sursa (job #2524682)
#include <bits/stdc++.h>
#define oo 2000000000
using namespace std;
char s[102];
int a[102][102];
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
int n, m, d[105][105], dist[105][105], xj, yj, xr, yr;
queue < pair<int, int> >q;
inline bool Inside(int i, int j)
{
return i <= n && i >= 1 && j <= m && j >= 1;
}
ifstream fin("rj.in");
ofstream fout("rj.out");
void Leeromeo()
{
int i, j, x, y, k;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
d[i][j] = oo;
d[xr][yr] = 1;
q.push({xr, yr});
while(!q.empty())
{
i = q.front().first;
j = q.front().second;
q.pop();
for(k = 0; k < 8; k++)
{
x = i + dx[k];
y = j + dy[k];
if(Inside(x, y) && a[x][y] == 0 && d[x][y] > d[i][j] + 1)
{
d[x][y] = d[i][j] + 1;
q.push({x, y});
}
}
}
}
void Leejulieta()
{
int i, j, x, y, k;
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
dist[i][j] = oo;
dist[xj][yj] = 1;
q.push({xj, yj});
while(!q.empty())
{
i = q.front().first;
j = q.front().second;
q.pop();
for(k = 0; k < 8; k++)
{
x = i + dx[k];
y = j + dy[k];
if(Inside(x, y) && a[x][y] == 0 && dist[x][y] > dist[i][j] + 1)
{
dist[x][y] = dist[i][j] + 1;
q.push({x, y});
}
}
}
}
int main()
{
int i, j, minim = oo, minimi, minimj;
fin >> n >> m;
fin.get();
for(i = 1; i <= n; i++)
{
fin.getline(s + 1, 102);
for(j = 1; j <= m; j++)
{
if(s[j] == ' ')
a[i][j] = 0;
else if(s[j] == 'X')
a[i][j] = 1;
else if(s[j] == 'R')
{
xr = i;
yr = j;
}
else if(s[j] == 'J')
{
xj = i;
yj = j;
}
}
}
Leeromeo();
Leejulieta();
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
if(d[i][j] != oo && dist[i][j] != oo && d[i][j] == dist[i][j])
if(d[i][j] < minim)
{
minim = d[i][j];
minimi = i;
minimj = j;
}
fout << minim << " " << minimi << " " << minimj;
return 0;
}