Cod sursa(job #657167)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 5 ianuarie 2012 21:20:28
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#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;
}