Pagini recente » Cod sursa (job #2886927) | Cod sursa (job #791877)
Cod sursa(job #791877)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define nmax 105
#define inf 99999999
#define x first
#define y second
using namespace std;
char a[nmax][nmax];
int costr[nmax][nmax], costj[nmax][nmax];
int n, m;
vector < pair <int, int> > ind;
pair <int, int> rm, jl, nod;
queue < pair <int, int> > q;
void bfsr() {
costr[rm.x][rm.y] = 0;
q.push(make_pair(rm.x, rm.y));
while(!q.empty()) {
nod.x = q.front().x;
nod.y = q.front().y;
q.pop();
for(int i = 0; i < ind.size(); i++) {
int newx = nod.x + ind[i].x;
int newy = nod.y + ind[i].y;
if(newx >= 1 && newx <= n && newy >= 1 && newy <= m)
if(a[newx][newy] != 'X' && costr[newx][newy] == -1) {
costr[newx][newy] = costr[nod.x][nod.y] + 1;
q.push(make_pair(newx, newy));
}
}
}
}
void bfsj() {
costj[jl.x][jl.y] = 0;
while(!q.empty()) q.pop();
q.push(make_pair(jl.x, jl.y));
while(!q.empty()) {
nod.x = q.front().x;
nod.y = q.front().y;
q.pop();
for(int i = 0; i < ind.size(); i++) {
int newx = nod.x + ind[i].x;
int newy = nod.y + ind[i].y;
if(newx >= 1 && newx <= n && newy >= 1 && newy <= m)
if(a[newx][newy] != 'X' && costj[newx][newy] == -1) {
costj[newx][newy] = costj[nod.x][nod.y] + 1;
q.push(make_pair(newx, newy));
}
}
}
}
int main() {
ifstream f("rj.in");
ofstream g("rj.out");
int i, j;
f>>n>>m; //citire
f.get();
for(i=1; i<=n; i++) {
//cout<<"<";
for(j=1; j<=m; j++) {
a[i][j] = f.get();
if(a[i][j]=='R') rm.x = i, rm.y = j;
if(a[i][j]=='J') jl.x = i, jl.y = j;
//cout<<a[i][j];
}
f.get();
//cout<<">\n";
}
for(i=-1; i<=1; i++)
for(j=-1; j<=1; j++)
ind.push_back(make_pair(i, j));
for(i=0; i<=n+1; i++)
for(j=0; j<=m+1; j++)
costj[i][j] = -1, costr[i][j] = -1;
//cout<<rm.x<<" "<<rm.y<<"\n";
//cout<<jl.x<<" "<<jl.y<<"\n";
bfsr();
bfsj();
int solx=0, soly=0, minim = inf, timp;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(costr[i][j]!=-1 && costj[i][j]!=-1) {
timp = max(costr[i][j], costj[i][j]) + 1;
if(timp < minim && abs(costj[i][j]-costr[i][j]) == 0) {
minim = timp;
solx = i;
soly = j;
}
}
g<<minim<<" "<<solx<<" "<<soly<<"\n";
f.close();
g.close();
return 0;
}