Pagini recente » Cod sursa (job #1877259) | Cod sursa (job #2527849) | Monitorul de evaluare | Cod sursa (job #2786598) | Cod sursa (job #1204235)
#include <fstream>
#include <string.h>
#define NMax 105
#define INF 2000000000
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int n, m, rx, ry, jx, jy, i, j, p, u, lmin=INF, cmin=INF, tmin=INF, cx, cy;
short int vizr[NMax][NMax], vizj[NMax][NMax], qu[2][NMax*NMax], mat[NMax][NMax];
const int dx[]={0, 0, 1, 1, 1, 0, -1, -1, -1}, dy[]={0, -1, -1, 0, 1, 1, 1, 0, -1};
char line[150];
int main()
{
f>>n>>m;
f.getline(line, 140);
for (i=1; i<=n; i++) {
f.getline(line, 140);
for (j=0; j<m; j++) {
if (line[j] == ' ')
mat[i][j+1]=0;
else if(line[j] == 'X')
mat[i][j+1]=1;
else if(line[j]=='R') {
rx=i, ry=j+1;
}
else if(line[j]=='J') {
jx=i, jy=j+1;
}
}
}
vizr[rx][ry]=1;
qu[0][1]=rx;
qu[1][1]=ry;
p=u=1;
while (p<=u) {
for (i=1; i<=8; i++) {
int l=qu[0][p]+dx[i];
int c=qu[1][p]+dy[i];
if (mat[l][c]==0 && vizr[l][c]==0 && l>=1 && l<=n && c>=1 && c<=m) {
u++;
qu[0][u]=l;
qu[1][u]=c;
vizr[l][c] = vizr[ qu[0][p] ][ qu[1][p] ] + 1;
}
}
p++;
}
vizj[jx][jy]=1;
memset(qu, 0, sizeof(qu));
qu[0][1]=jx;
qu[1][1]=jy;
p=u=1;
while (p<=u) {
for (i=1; i<=8; i++) {
int l=qu[0][p]+dx[i];
int c=qu[1][p]+dy[i];
if (mat[l][c]==0 && vizj[l][c]==0 && l>=1 && l<=n && c>=1 && c<=m) {
u++;
qu[0][u]=l;
qu[1][u]=c;
vizj[l][c] = vizj[ qu[0][p] ][ qu[1][p] ] + 1;
}
}
p++;
}
for (i=1; i<=n; i++) {
for (j=1; j<=m; j++) {
if (mat[i][j]==0) {
if (vizr[i][j] == vizj[i][j] && vizr[i][j]!=0) {
if (vizr[i][j]<tmin) {
tmin=vizr[i][j];
cx=i;
cy=j;
lmin=i;
cmin=j;
}
else if (vizr[i][j]==tmin) {
if (lmin > i) {
tmin=vizr[i][j];
cx=i;
cy=j;
lmin=i;
}
else if(lmin==i) {
if (cmin > j) {
tmin=vizr[i][j];
cx=i;
cy=j;
cmin=j;
}
}
}
}
}
}
}
g<<tmin<<" "<<cx<<" "<<cy<<"\n";
return 0;
}