Pagini recente » Cod sursa (job #1254629) | Cod sursa (job #3033233) | Cod sursa (job #2080598) | Cod sursa (job #1587971) | Cod sursa (job #657167)
Cod sursa(job #657167)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int dx[8]={1,0,-1,-1,-1,0,1,1};
int dy[8]={1,1,1,0,-1,-1,-1,0};
int n,m,i,j,r[101][101],l[101][101],rl,rc,jl,jc,prim,ultim,dir,ii,jj,tmin;
short int coadai[10001],coadaj[10001],a[101][101];
char c;
int main () {
f >> n >> m;
for (i=0;i<=n+1;i++) a[i][0]=a[i][m+1]=-1; for (j=0;j<=m+1;j++) a[0][j]=a[n+1][j]=-1;
for (i=1;i<=n;i++) {
f.get();
for (j=1;j<=m;j++) {
f.get(c);r[i][j]=l[i][j]=2*n*m+1;
if (c=='X') a[i][j]=-1;
if (c=='R') {rl=i;rc=j;a[i][j]=3;}
if (c=='J') {jl=i;jc=j;a[i][j]=4;}
}
}
r[rl][rc]=1;prim=ultim=1;coadai[1]=rl;coadaj[1]=rc;
while (prim<=ultim) {
i=coadai[prim];j=coadaj[prim];
for (dir=0;dir<=7;dir++) {
ii=i+dx[dir];jj=j+dy[dir];
if (ii>=0 && jj>=0 && i>=0 && j>=0) {
if (a[ii][jj]>=0 && r[ii][jj]>r[i][j]+1) {
r[ii][jj]=r[i][j]+1;ultim++;coadai[ultim]=ii;coadaj[ultim]=jj;}
}}
prim++;
}
memset(coadai,0,10001);memset(coadaj,0,10001);
l[jl][jc]=1;prim=ultim=1;coadai[1]=jl;coadaj[1]=jc;
while (prim<=ultim) {
i=coadai[prim];j=coadaj[prim];
for (dir=0;dir<=7;dir++) {
ii=i+dx[dir];jj=j+dy[dir];
if (ii>=0 && jj>=0 && i>=0 &j>=0) {
if (a[ii][jj]>=0 && l[ii][jj]>l[i][j]+1) {
l[ii][jj]=l[i][j]+1;ultim++;coadai[ultim]=ii;coadaj[ultim]=jj;}
}}
prim++;
}ii=0;jj=0;tmin=2*m*n+1;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
if (r[i][j]==l[i][j] && tmin>r[i][j]) {
tmin=r[i][j];
ii=i;
jj=j;
}
g << tmin << ' ' << ii << ' '<< jj << '\n';
f.close();g.close();
return 0;
}