Pagini recente » Cod sursa (job #592129) | Cod sursa (job #1798537) | Cod sursa (job #1715397) | Cod sursa (job #2295551) | Cod sursa (job #2668547)
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
struct cell{
int x, y;
};
queue<cell> q1, q2;
int N, M;
int mat1[1010][1010], mat2[1010][1010];
void bfs12 (cell start1, cell start2){
int x, y;
cell poz, aux;
mat1[start1.x][start1.y] = mat2[start2.x][start2.y] = 1;
q1.push(start1);
q2.push(start2);
while(!q1.empty()){
poz = q1.front();
q1.pop();
//g<<"Consider elementul x="<<poz.x<<" y="<<poz.y<<" elem="<<mat1[poz.x][poz.y]<<endl;
for(x=-1; x<=1; x++)
for(y=-1; y<=1; y++){
aux.x = poz.x + x;
aux.y = poz.y + y;
//g<<(aux.x<N)<<" "<<(aux.x>=0)<<" "<<(aux.y<M)<<" "<<(aux.y>=0)<<" "<<(x!=0 || y!=0)<<" "<<(mat1[aux.x][aux.y]==0)<<"\n\n\n";
if((aux.x<=N && aux.x>=1) && (aux.y<=M && aux.y>=1) && (x!=0 || y!=0)){
if(mat1[aux.x][aux.y]==0 && mat1[aux.x][aux.y]!=-1){
mat1[aux.x][aux.y] = mat1[poz.x][poz.y] + 1;
q1.push(aux);
//g<<mat1[aux.x][aux.y]<<" "<<aux.x<<" "<<aux.y<<"\n";
}
}
}
}
while(!q2.empty()){
poz = q2.front();
q2.pop();
//g<<"Consider elementul x="<<poz.x<<" y="<<poz.y<<" elem="<<mat2[poz.x][poz.y]<<endl;
for(x=-1; x<=1; x++)
for(y=-1; y<=1; y++){
aux.x = poz.x + x;
aux.y = poz.y + y;
//g<<(aux.x<N)<<" "<<(aux.x>=0)<<" "<<(aux.y<M)<<" "<<(aux.y>=0)<<" "<<(x!=0 || y!=0)<<" "<<(mat1[aux.x][aux.y]==0)<<"\n\n\n";
if((aux.x<=N && aux.x>=1) && (aux.y<=M && aux.y>=1) && (x!=0 || y!=0)){
if(mat2[aux.x][aux.y]==0 && mat2[aux.x][aux.y]!=-1){
mat2[aux.x][aux.y] = mat2[poz.x][poz.y] + 1;
q2.push(aux);
//g<<mat2[aux.x][aux.y]<<" "<<mat2[poz.x][poz.y]<<"\n";
}
}
}
}
}
int main(){
f>>N>>M;
char line[105];
int i, j, trez=105;
cell rom, jul, rez;
f.get();
for(i=0; i<N; i++){
f.getline(line, M+5);
for(j=0; j<M; j++){
if(line[j]=='R'){
mat1[i+1][j+1] = mat2[i+1][j+1] = 0;
rom.x = i+1;
rom.y = j+1;
}
else if(line[j]=='J'){
mat1[i+1][j+1] = mat2[i+1][j+1] = 0;
jul.x = i+1;
jul.y = j+1;
}
else if(line[j]=='X')
mat1[i+1][j+1] = mat2[i+1][j+1] = -1;
else if(line[j]==' ')
mat1[i+1][j+1] = mat2[i+1][j+1] = 0;
}
}
bfs12(rom, jul);
/*for (i=1; i<=N; i++){
g<<endl;
for(j=1; j<=M; j++){
g<<mat1[i][j]<<" ";
}
}
g<<"\n\n\n";
for (i=1; i<=N; i++){
g<<endl;
for(j=1; j<=M; j++){
g<<mat2[i][j]<<" ";
}
}*/
for (i=1; i<=N; i++)
for(j=1; j<=M; j++)
if(mat1[i][j]<trez && mat2[i][j]==mat1[i][j] && mat1[i][j]>0){
trez = mat1[i][j];
rez.x = i;
rez.y = j;
}
g<<trez<<" "<<rez.x<<" "<<rez.y;
return 0;
}