Pagini recente » Cod sursa (job #1359197) | Cod sursa (job #1287619) | Cod sursa (job #1858305) | Cod sursa (job #987570) | Cod sursa (job #2249828)
#include <iostream>
#include <queue>
#include <fstream>
#include <sstream>
using namespace std;
int N, M, ri, rj, ji, jj;
bool harta[102][102];
int romeo[102][102], julieta[102][102];
ifstream in("rj.in");
ofstream out("rj.out");
queue < pair < int, int > > Q;
int dx[8] = {-1,-1,-1,0,0,1,1,1},
dy[8] = {-1,0,1,-1,1,-1,0,1};
void read() {
in>>N>>M;
int k_line = 0;
std::string line;
while(std::getline(in, line)) {
for(int j=0; j<M; j++) {
harta[k_line][j+1] = (line[j] == ' ')? true : false;
if(line[j] == 'R')
ri = k_line, rj = j+1;
else if(line[j] == 'J')
ji = k_line, jj = j+1;
}
k_line += 1;
}
romeo[ri][rj] = 1;
julieta[ji][jj] = 1;
}
bool OK(int x, int y) {
if(x<1 || x>N || y<1 || y>M)
return false;
if(harta[x][y] == false)
return false;
if((x == ri && y == rj) || (x == ji && y == jj))
return false;
return true;
}
void romjul() {
// romeo
Q.push(make_pair(ri,rj));
while(!Q.empty()) {
int i = Q.front().first,
j = Q.front().second;
Q.pop();
for(int k=0; k<8; k++) {
int ni = i + dx[k],
nj = j + dy[k];
if(OK(ni, nj)) {
if(romeo[ni][nj] == 0) {
romeo[ni][nj] = romeo[i][j] + 1;
Q.push(make_pair(ni,nj));
}
}
}
}
// julieta
Q.push(make_pair(ji,jj));
while(!Q.empty()) {
int i = Q.front().first,
j = Q.front().second;
Q.pop();
for(int k=0; k<8; k++) {
int ni = i + dx[k],
nj = j + dy[k];
if(OK(ni, nj)) {
if(julieta[ni][nj] == 0) {
julieta[ni][nj] = julieta[i][j] + 1;
Q.push(make_pair(ni,nj));
}
}
}
}
}
void find() {
bool gasit = false;
int x, y, val;
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++) {
if(romeo[i][j] == julieta[i][j] && romeo[i][j]>0)
if(!gasit || romeo[i][j]<val)
val = romeo[i][j], gasit = true, x = i, y = j;
}
out<<val<<" "<<x<<" "<<y;
}
int main() {
read();
romjul();
find();
}