Pagini recente » Cod sursa (job #1130782) | Cod sursa (job #57320) | Cod sursa (job #2689019) | Cod sursa (job #2444678) | Cod sursa (job #2305419)
#include <bits/stdc++.h>
#define inf 1000007
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
char s[105];
int b[105][105], c[105][105], n, m, sx, sy, fx, fy;
int dx[] = {1, -1, 0, 0, 1, -1, -1, 1};
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
queue < pair < int, int > > Q;
void Citire()
{
int i, j;
fin >> n >> m;
for(i = 0; i <= n; i++)
{
fin.getline(s + 1, 105);
for(j = 1; j <= m; j++)
{
if(s[j] == ' ')
{
b[i][j] = inf;
c[i][j] = inf;
}
else if(s[j] == 'X')
{
b[i][j] = -1;
c[i][j] = -1;
}
else if(s[j] == 'R')
{
b[i][j] = 1;
c[i][j] = inf;
sx = i;
sy = j;
}
else if(s[j] == 'J')
{
b[i][j] = inf;
c[i][j] = 1;
fx = i;
fy = j;
}
}
}
}
void Bordare()
{
int i;
for(i = 0; i <= n + 1; i++)
b[i][0] = b[i][m + 1] = c[i][0] = c[i][m + 1] = -1;
for(i = 0; i <= m + 1; i++)
b[0][i] = b[n + 1][i] = c[i][0] = c[i][m + 1] = -1;
}
void Lee()
{
int k, ok, i, j, x, y, mn = inf + 1;
Q.push({sx, sy});
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(b[x][y] != -1 && b[x][y] > b[i][j] + 1)
{
b[x][y] = b[i][j] + 1;
Q.push({x, y});
}
}
}
Q.push({fx, fy});
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(c[x][y] != -1 && c[x][y] > c[i][j] + 1)
{
c[x][y] = c[i][j] + 1;
Q.push({x, y});
}
}
}
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m ; j++)
if(b[i][j] != -1 && b[i][j] == c[i][j] && mn > b[i][j])
{
mn = b[i][j];
x = i;
y = j;
}
}
fout << b[x][y] << " " << x << " " << y << "\n";
fout.close();
}
int main()
{
Citire();
Bordare();
Lee();
return 0;
}