Pagini recente » Cod sursa (job #912213) | Cod sursa (job #1797547) | Cod sursa (job #2531894) | Cod sursa (job #956162) | Cod sursa (job #2541874)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
queue < pair < int , int > > q;
int n,m;
int mat[105][105];
char sir[105];
int adiac1[105][105];
int adiac2[105][105];
int linrom,colrom,linjul,coljul;
int dx[5]={0,-1,0,1,0}, dy[5]={0,0,1,0,-1};
int lin,col;
int dist;
void bordare() {
for (int i=1;i<=n;i++) {
mat[i][0]=-1;
mat[i][m+1]=-1;
}
for (int j=1;j<=m;j++) {
mat[0][j]=-1;
mat[n+1][j]=-1;
}
}
void lee1() {
while (q.empty()==0) {
lin = q.front().first;
col= q.front().second;
for (int k=1;k<=4;k++) {
if (mat[lin+dx[k]][col+dy[k]]==0 && (adiac1[lin+dx[k]][col+dy[k]]>adiac1[lin][col]+1 || adiac1[lin+dx[k]][col+dy[k]]==0)) {
adiac1[lin+dx[k]][col+dy[k]]=adiac1[lin][col]+1;
q.push(make_pair(lin+dx[k],col+dy[k]));
}
}
q.pop();
}
}
void lee2() {
while (q.empty()==0) {
lin = q.front().first;
col= q.front().second;
for (int k=1;k<=4;k++) {
if (mat[lin+dx[k]][col+dy[k]]==0 && (adiac2[lin+dx[k]][col+dy[k]]>adiac2[lin][col]+1 || adiac2[lin+dx[k]][col+dy[k]]==0)) {
adiac2[lin+dx[k]][col+dy[k]]=adiac2[lin][col]+1;
q.push(make_pair(lin+dx[k],col+dy[k]));
}
}
q.pop();
}
}
int main()
{
f >> n >> m;
f.get();
bordare();
for (int i=1;i<=n;i++) {
f.getline(sir,100);
for (int j=0;j<m;j++) {
if (sir[j]==' ') {
mat[i][j+1]=0;
}
else if (sir[j]=='X') {
mat[i][j+1]=-1;
}
else if (sir[j]=='R') {
linrom=i;
colrom=j+1;
mat[i][j+1]=0;
}
else if(sir[j]=='J') {
linjul=i;
coljul=j+1;
mat[i][j+1]=0;
}
}
}
q.push(make_pair(linjul,coljul));
adiac1[linjul][coljul]=1;
lee1();
q.push(make_pair(linrom,colrom));
adiac2[linrom][colrom]=1;
lee2();
/*for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
g << mat[i][j];
}
g <<'\n';
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
g << adiac1[i][j];
}
g <<'\n';
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
g << adiac2[i][j];
}
g <<'\n';
}
g << linjul <<" "<<coljul<<" "<<linrom<<" "<<colrom;
*/
dist = adiac1[linrom][colrom]+1;
dist/=2;
int ok=0;
for (int i=1;i<=n && ok==0;i++) {
for (int j=1;j<=m && ok==0;j++) {
if (adiac1[i][j]==dist && adiac2[i][j]==dist) {
g << dist-1 <<" " << i <<" "<< j;
ok=1;
}
}
}
return 0;
}