Pagini recente » Cod sursa (job #1247604) | Cod sursa (job #1683755) | Cod sursa (job #376856) | Cod sursa (job #1861229) | Cod sursa (job #1932676)
#include <fstream>
#include <queue>
using namespace std ;
ifstream cin ("rj.in") ;
ofstream cout ("rj.out") ;
const int MAX = 179 ;
queue < pair<int, int> > Q;
char sir[MAX];
bool cant [MAX][MAX] ;
int distr [MAX][MAX] ;
int distj [MAX] [MAX];
int dx[] = {1, -1, 0, 0, 1, 1, -1, -1} ;
int dy[] = {0, 0, -1, 1, 1, -1, 1, -1} ;
bool inside (int i, int j, int n, int m)
{
return i >= 1 and j >= 1 and i <= n and j <= m ;
}
int main ()
{
int n, m ;
cin >> n >> m ;
cin.get();
int xr, yr, xj, yj;
for (int i=1; i<=n; i++){
cin.getline(sir+1, MAX);
for (int j=1; j<=m; j++){
if (sir[j]=='R'){
xr=i;
yr=j;
}
if (sir[j]=='J'){
xj=i;
yj=j;
}
if (sir[j]=='X'){
cant [i][j] = true;
}
distr [i][j] = 1e9 ;
distj [i][j] = 1e9 ;
}
}
//cout<<xr<<" "<<yr<<" "<<xj<<" "<<yj;
distr [xr][yr] = 1 ;
int xr_neigh;
int yr_neigh;
Q.push (make_pair(xr,yr)) ;
while (!Q.empty()) {
pair <int, int> curr = Q.front() ;
Q.pop() ;
for (int k = 0; k <= 7; ++ k) {
xr_neigh = curr.first + dx [k] ;
yr_neigh = curr.second + dy [k] ;
if (inside (xr_neigh, yr_neigh, n, m) == false) {
continue ;
}
if (cant [xr_neigh][yr_neigh] == true) {
continue ;
}
if (distr [xr_neigh][yr_neigh] > distr [curr.first][curr.second] + 1) {
distr [xr_neigh][yr_neigh] = distr [curr.first][curr.second] + 1 ;
Q.push (make_pair (xr_neigh, yr_neigh)) ;
}
}
}
int xj_neigh;
int yj_neigh;
distj [xj][yj] = 1 ;
Q.push (make_pair(xj,yj)) ;
while (!Q.empty()) {
pair <int, int> curj = Q.front() ;
Q.pop() ;
for (int k = 0; k <= 7; ++ k) {
xj_neigh = curj.first + dx [k] ;
yj_neigh = curj.second + dy [k] ;
if (inside (xj_neigh, yj_neigh, n, m) == false) {
continue ;
}
if (cant [xj_neigh][yj_neigh] == true) {
continue ;
}
if (distj [xj_neigh][yj_neigh] > distj [curj.first][curj.second] + 1) {
distj [xj_neigh][yj_neigh] = distj [curj.first][curj.second] + 1 ;
Q.push (make_pair (xj_neigh, yj_neigh)) ;
}
if (distr [xj_neigh][yj_neigh]==distj [xj_neigh][yj_neigh]){
cout<<distj [xj_neigh][yj_neigh]<<" "<<xj_neigh<<" "<<yj_neigh;
return 0;
}
}
}
return 0 ;
}