Pagini recente » Cod sursa (job #749401) | Cod sursa (job #2011077) | Cod sursa (job #3329375) | Cod sursa (job #2116121) | Cod sursa (job #791880)
Cod sursa(job #791880)
#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 cost[2][nmax][nmax];
int n, m;
vector < pair <int, int> > ind;
pair <int, int> nod, protagonist[2];
queue < pair <int, int> > q;
int nu_iese_cumva_din_matrice(int newx, int newy) {
if(newx >= 1 && newx <= n && newy >= 1 && newy <= m) return 1;
return 0;
}
void bfs(int p) {
cost[p][protagonist[p].x][protagonist[p].y] = 0;
q.push(make_pair(protagonist[p].x, protagonist[p].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(nu_iese_cumva_din_matrice(newx, newy))
if(a[newx][newy] != 'X' && cost[p][newx][newy] == -1) {
cost[p][newx][newy] = cost[p][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++) {
for(j=1; j<=m; j++) {
a[i][j] = f.get();
if(a[i][j]=='R') protagonist[0].x = i, protagonist[0].y = j;
if(a[i][j]=='J') protagonist[1].x = i, protagonist[1].y = j;
}
f.get();
}
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++)
cost[0][i][j] = -1, cost[1][i][j] = -1;
bfs(0); //pentru ROMEO
bfs(1); //si pentru JULIETA
int solx=0, soly=0, minim = inf, timp;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if(cost[0][i][j]!=-1 && cost[1][i][j]!=-1) {
timp = max(cost[0][i][j], cost[1][i][j]) + 1;
if(timp < minim && abs(cost[1][i][j]-cost[0][i][j]) == 0) {
minim = timp;
solx = i;
soly = j;
}
}
g<<minim<<" "<<solx<<" "<<soly<<"\n";
f.close();
g.close();
return 0;
}