Pagini recente » Cod sursa (job #2918404) | Cod sursa (job #2395044) | Cod sursa (job #3138207) | Cod sursa (job #2999233) | Cod sursa (job #2857679)
#include <fstream>
#include <queue>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
int r[105][105], ju[105][105], di[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dj[] = {0, 1, 1, 1, 0, -1, -1, -1}, n, m, i, j;
char a[105][105];
queue < pair <int, int> > Q;
bool inmat(int x, int y)
{
return x >= 0 && x < n && y >= 0 && y < m;
}
void Lee1(int istart, int jstart) {
r[istart][jstart] = 1;
Q.push({istart, jstart});
while(! Q.empty()) {
int i = Q.front().first;
int j = Q.front().second;
for(int k = 0 ; k < 8 ; ++k) {
int iv = i + di[k];
int jv = j + dj[k];
if(inmat(iv, jv) && (r[iv][jv] == 0 || r[iv][jv] > r[i][j] + 1)) {
r[iv][jv] = r[i][j] + 1;
Q.push({iv, jv});
}
}
Q.pop();
}
}
void Lee2(int istart, int jstart) {
ju[istart][jstart] = 1;
Q.push({istart, jstart});
while(! Q.empty()) {
int i = Q.front().first;
int j = Q.front().second;
for(int k = 0 ; k < 8 ; ++k) {
int iv = i + di[k];
int jv = j + dj[k];
if(inmat(iv, jv) && (ju[iv][jv] == 0 || ju[iv][jv] > ju[i][j] + 1)) {
ju[iv][jv] = ju[i][j] + 1;
Q.push({iv, jv});
}
}
Q.pop();
}
}
int main()
{
int minv = 1e9 + 1, imin, jmin, ir, jr, ij, jj;
in >> n >> m;
in.get();
for(i = 0 ; i < n ; ++i){
in.getline(a[i], 105);
for(j = 0 ; j < m ; ++j){
if(a[i][j] == ' '){
r[i][j] = 0;
ju[i][j] = 0;
}
if(a[i][j] == 'X'){
r[i][j] = -1;
ju[i][j] = -1;
}
if(a[i][j] == 'R') {
ir = i;
jr = j;
r[i][j] = 0;
ju[i][j] = 0;
}
if(a[i][j] == 'J') {
ij = i;
jj = j;
r[i][j] = 0;
ju[i][j] = 0;
}
}
}
Lee1(ir, jr);
Lee2(ij, jj);
for(i = 0 ; i < n ; ++i){
for(j = 0 ; j < m ; ++j){
if(r[i][j] == ju[i][j] && r[i][j]!= -1 && r[i][j] != 0) {
if(r[i][j] < minv){
minv = r[i][j];
imin = i;
jmin = j;
}
}
}
}
out << minv << " " << imin + 1 << " " << jmin + 1 ;
return 0;
}