Pagini recente » Cod sursa (job #1531074) | Cod sursa (job #176453) | Cod sursa (job #1679426) | Cod sursa (job #822549) | Cod sursa (job #1655851)
#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
const int MAXN = 101;
const int DIRECTIONS = 8;
int n, m;
char A[MAXN][MAXN];
const int dirX[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dirY[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dR[MAXN][MAXN];
int dJ[MAXN][MAXN];
int rX;
int rY;
int jX;
int jY;
void read() {
in >> n;
in >> m;
in.get();
char c;
string s;
for(int i = 1; i <= n; i++) {
getline(in, s);
for(int j = 0; j < s.size(); j++) {
A[i][j + 1] = s[j];
if(s[j] == 'J')
jX = i, jY = j + 1;
if(s[j] == 'R')
rX = i, rY = j + 1;
}
}
}
bool checkRomeo(int i, int j) {
//prevent initial state
if(i == rX && j == rY)
return false;
if(A[i][j] == 'X')
return false;
if(i < 0 || i > n)
return false;
if(j < 0 || j > m)
return false;
if(dR[i][j] > 0)
return false;
return true;
}
bool checkJuliet(int i, int j) {
//prevent initial state
if(i == jX && j == jY)
return false;
if(A[i][j] == 'X')
return false;
if(i < 0 || i > n)
return false;
if(j < 0 || j > m)
return false;
if(dJ[i][j] > 0)
return false;
return true;
}
void solve() {
queue< pair<int, int> > qR;
queue< pair<int, int> > qJ;
qR.push(make_pair(rX, rY));
qJ.push(make_pair(jX, jY));
while(qR.empty() == false && qJ.empty() == false) {
int rX = qR.front().first;
int rY = qR.front().second;
int jX = qJ.front().first;
int jY = qJ.front().second;
qR.pop();
qJ.pop();
for(int i = 0; i < DIRECTIONS; i++) {
if(checkRomeo(rX + dirX[i], rY + dirY[i]) == true ) {
dR[rX + dirX[i]][rY + dirY[i]] = dR[rX][rY] + 1;
qR.push(make_pair(rX + dirX[i], rY + dirY[i]));
}
if(checkJuliet(jX + dirX[i], jY + dirY[i]) == true) {
dJ[jX + dirX[i]][jY + dirY[i]] = dJ[jX][jY] + 1;
qJ.push(make_pair(jX + dirX[i], jY + dirY[i]));
}
}
}
}
void write() {
int minn = 1 << 20;
int x = 0;
int y = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(dR[i][j] == dJ[i][j]) {
if(dR[i][j] < minn && dR[i][j] > 0) {
minn = dR[i][j];
x = i;
y = j;
}
}
}
}
out << minn + 1 << " " << x << " " << y <<"\n";
/*out << "MATRICE\n";
out << "ROMEO \n";
for(int i = 1; i <= n; i++) {
for(int j = 1; j<= m; j++) {
out << A[i][j] << " ";
}
out << endl;
}
out << "ROMEO \n";
for(int i = 1; i <= n; i++) {
for(int j = 1; j<= m; j++) {
out << dR[i][j] << " ";
}
out << endl;
}
out << "\nJULIETA \n";
for(int i = 1; i <= n; i++) {
for(int j = 1; j<= m; j++) {
out << dJ[i][j] << " ";
}
out << endl;
}
*/
}
int main() {
read();
solve();
write();
return 0;
}