Pagini recente » Cod sursa (job #231378) | Cod sursa (job #676396) | Cod sursa (job #2124449) | Cod sursa (job #616159) | Cod sursa (job #2034095)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream in ("rj.in");
ofstream out ("rj.out");
int const nmax = 100;
char v[1 + nmax][1 + nmax];
struct Square{
int x;
int y;
};
int const iplus[8] = {0 ,0 , 1 ,1 ,1 ,-1 ,-1 ,-1};
int const jplus[8] = {1 ,-1 ,0 ,1, -1 ,0 ,1 , -1};
int n , m;
int distr[5 + nmax][5 + nmax];
int distj[5 + nmax][5 + nmax];
void bfs(){
queue<Square> q;
for(int i = 1 ; i <= n ;i++){
for(int j = 1 ; j <= m ;j++){
if(v[i][j] == 'R'){
distr[i][j] = 1;
q.push({i , j});
} else{
distr[i][j] = -1;
}
}
}
while(0 < q.size()){
int x = q.front().x;
int y = q.front().y;
q.pop();
for(int h = 0 ; h < 8 ;h++){
int newx = x + iplus[h];
int newy = y + jplus[h];
if(v[newx][newy] == ' ' && (distr[newx][newy] == -1 || distr[x][y] + 1 < distr[newx][newy] ) ){
q.push({newx , newy});
distr[newx][newy] = distr[x][y] + 1;
}
}
}
for(int i = 1 ; i <= n ;i++){
for(int j = 1 ; j <= m ;j++){
if(v[i][j] == 'J'){
distj[i][j] = 1;
q.push({i , j});
} else{
distj[i][j] = -1;
}
}
}
while(0 < q.size()){
int x = q.front().x;
int y = q.front().y;
q.pop();
for(int h = 0 ; h < 8 ;h++){
int newx = x + iplus[h];
int newy = y + jplus[h];
if(v[newx][newy] == ' ' && (distj[newx][newy] == -1 || distj[x][y] + 1 < distj[newx][newy] ) ){
q.push({newx , newy});
distj[newx][newy] = distj[x][y] + 1;
}
}
}
}
int main()
{
in>>n>>m;
in>>noskipws;
char c;
for(int i = 1 ; i <= n ;i++){
in>>c;///endline
for(int j = 1 ; j <= m ;j++){
in>>v[i][j];
//cout<<v[i][j];
}
//cout<<'\n';
}
bfs();
int smax = 1000000000;
int x = 0, y = 0;
for(int i = 1 ; i <= n ;i++){
for(int j = 1 ; j <= m ;j++){
if(distj[i][j] == distr[i][j] && 0 < distj[i][j]){
if(distj[i][j] < smax){
smax = distj[i][j];
x = i;
y = j;
}
}
}
}
out<<smax<<" "<<x<<" "<<y;
return 0;
}