Pagini recente » Cod sursa (job #2441589) | Cod sursa (job #1231594) | Cod sursa (job #1971823) | Cod sursa (job #2195753) | Cod sursa (job #704697)
Cod sursa(job #704697)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
short oras[101][101];
short a[101][101],b[101][101];
int xj,yr,yj,xr;
int N,M;
int Min = 100000,Mini,Minj;
struct q {
int x;
int y;
};
queue <q> coada;
ifstream f("rj.in");
ofstream g("rj.out");
int inside_the_matrix(int x, int y)
{
return x >= 1 || y >= 1 || x <= N || y <= M || oras[x][y] != 'X';
}
int BFS(int x, int y, short mat[][101]) {
q aux;
aux.x = x;
aux.y = y;
mat[x][y] = 1;
coada.push(aux);
while(!coada.empty()) {
x = coada.front().x;
y = coada.front().y;
coada.pop();
if(inside_the_matrix(x - 1, y) && mat[x][y] + 1 < mat[x-1][y]) {
mat[x-1][y] = mat[x][y] + 1;
aux.x = x-1;
aux.y = y;
coada.push(aux);
}
if(inside_the_matrix(x + 1, y) && mat[x][y] + 1 < mat[x+1][y]) {
mat[x+1][y] = mat[x][y] + 1;
aux.x = x+1;
aux.y = y;
coada.push(aux);
}
if(inside_the_matrix(x, y - 1) && mat[x][y] + 1 < mat[x][y-1]) {
mat[x][y-1] = mat[x][y] + 1;
aux.x = x;
aux.y = y-1;
coada.push(aux);
}
if(inside_the_matrix(x, y + 1) && mat[x][y] + 1 < mat[x][y+1]) {
mat[x][y+1] = mat[x][y] + 1;
aux.x = x;
aux.y = y+1;
coada.push(aux);
}
if(inside_the_matrix(x - 1, y - 1) && mat[x][y] + 1 < mat[x-1][y-1]) {
mat[x-1][y-1] = mat[x][y] + 1;
aux.x = x-1;
aux.y = y-1;
coada.push(aux);
}
if(inside_the_matrix(x - 1, y + 1) && mat[x][y] + 1 < mat[x-1][y+1]) {
mat[x-1][y+1] = mat[x][y] + 1;
aux.x = x-1;
aux.y = y+1;
coada.push(aux);
}
if(inside_the_matrix(x + 1, y - 1) && mat[x][y] + 1 < mat[x+1][y-1]) {
mat[x+1][y-1] = mat[x][y] + 1;
aux.x = x+1;
aux.y = y-1;
coada.push(aux);
}
if(inside_the_matrix(x + 1, y + 1) && mat[x][y] + 1 < mat[x+1][y+1]) {
mat[x+1][y+1] = mat[x][y] + 1;
aux.x = x+1;
aux.y = y+1;
coada.push(aux);
}
}
}
void find()
{
int i,j;
for(i = 1; i <= N; i++) {
for(j = 1; j <= M ; j++) {
if(a[i][j] == b[i][j] && a[i][j] != 10000 && a[i][j] != 0 && a[i][j] != -1) {
if(a[i][j] < Min) {
Min = a[i][j];
Mini = i;
Minj = j;
}
}
}
}
}
int main()
{
char sir[100];
int i,j;
f>>N>>M;
f.get();
for(i = 1; i <= N; i++) {
f.getline(sir,M+1);
for(j = 0 ; j < M ; j++) {
if(sir[j] == ' ') {
oras[i][j+1] = 0;
a[i][j+1] = 10000;
b[i][j+1] = 10000;
} else if(sir[j] == 'X') {
oras[i][j+1] = 1;
a[i][j+1] = -1;
b[i][j+1] = -1;
} else if(sir[j] == 'R') {
oras[i][j+1] = 2;
xr = i;
yr = j+1;
} else if(sir[j] == 'J') {
oras[i][j+1] = 3;
xj = i;
yj = j+1;
}
}
}
BFS(xr,yr,a);
BFS(xj,yj,b);
find();
g<<Min<<" "<<Mini<<" "<<Minj;
}