Pagini recente » Cod sursa (job #854022) | Cod sursa (job #2800292) | Cod sursa (job #616678) | Cod sursa (job #3250992) | Cod sursa (job #3205261)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream cin("rj.in");
ofstream cout("rj.out");
queue<pair<int,int>>q;
vector<vector<char>>mat;
vector<vector<int>>distanta;
vector<int>x={1,-1,0,0,1,1,-1,-1},y={0,0,1,-1,-1,1,-1,1};
const int inf=1e9;
void bfs(int n,int m,int& rasp,int& a,int& b){
while(!q.empty()){
pair<int,int>poz=q.front();
q.pop();
int i,j;
for(int u=0;u<=3;u++){
i=poz.first+x[u];
j=poz.second+y[u];
if(i>n || i<1 || j>m || j<1 || mat[i][j]=='X'){
continue;
}
if(distanta[i][j]>distanta[poz.first][poz.second]+1){
distanta[i][j]=distanta[poz.first][poz.second]+1;
q.push({i,j});
}else if(distanta[i][j]==distanta[poz.first][poz.second]+1){
if(rasp>distanta[i][j]){
rasp=distanta[i][j];
a=i;
b=j;
}else if(rasp==distanta[i][j]){
if(a>i || (a>=i && b>=j)){
a=i;
b=j;
}
}
q.push({i,j});
}
}
}
}
int main(){
int n,m;
cin>>n>>m;
mat.resize(n+1,vector<char>(m+1));
distanta.resize(n+1,vector<int>(m+1,inf));
string s;
for(int i=0;i<=n;i++){
getline(cin,s);
for(int j=0;j<s.size();j++){
mat[i][j+1]=s[j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mat[i][j]=='R' or mat[i][j]=='J'){
distanta[i][j]=0;
q.push({i,j});
}
}
}
int a=-1,b=-1,rasp=1e9;
bfs(n,m,rasp,a,b);
cout<<rasp<<" "<<a<<" "<<b;
}