Cod sursa(job #1891305)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 23 februarie 2017 21:41:57
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
# include <fstream>
# include <bitset>
# define DIM 103
# define INF 1000000000
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
bitset<DIM> v[DIM],f[DIM];
char t[DIM];
short c[2][DIM*DIM];
int di[]={1,1,1,-1,-1,-1,0,0};
int dj[]={1,-1,0,1,-1,0,1,-1};
int r[DIM][DIM],j[DIM][DIM];
int n,m,ii,jj,d,irs,jrs,ijs,jjs;
int ic,jc,iv,jv,p,u,soli,solj,minim=INF;
int main () {
    fin>>n>>m;
    fin.getline(t,DIM-1);
    for(ii=1;ii<=n;ii++){
        fin.getline(t,DIM-1);
        for(jj=1;jj<=m;jj++){
            if(t[jj-1]=='X')
                v[ii][jj]=1;
            if(t[jj-1]=='R'){
                irs=ii;
                jrs=jj;
            }
            if(t[jj-1]=='J'){
                ijs=ii;
                jjs=jj;
            }
            f[ii][jj]=v[ii][jj];
        }
    }
    c[0][++u]=irs;
    c[1][++p]=jrs;
    v[irs][jrs]=1;
    while(p<=u){
        ic=c[0][p];
        jc=c[1][p++];
        for(int d=0;d<8;d++){
            iv=ic+di[d];
            jv=jc+dj[d];
            if(iv>=1&&iv<=n&&jv>=1&&jv<=m&&v[iv][jv]==0){
                v[iv][jv]=1;
                r[iv][jv]=r[ic][jc]+1;
                c[0][++u]=iv;
                c[1][u]=jv;
            }
        }
    }
    p=0;
    u=0;
    c[0][++u]=ijs;
    c[1][++p]=jjs;
    v[ijs][jjs]=1;
    while(p<=u){
        ic=c[0][p];
        jc=c[1][p++];
        for(int d=0;d<8;d++){
            iv=ic+di[d];
            jv=jc+dj[d];
            if(iv>=1&&iv<=n&&jv>=1&&jv<=m&&f[iv][jv]==0){
                f[iv][jv]=1;
                j[iv][jv]=j[ic][jc]+1;
                c[0][++u]=iv;
                c[1][u]=jv;
            }
        }
    }
    for(ii=1;ii<=n;ii++)
        for(jj=1;jj<=m;jj++)
            if(r[ii][jj]==j[ii][jj]&&r[ii][jj]<minim&&r[ii][jj]>0){
                minim=r[ii][jj];
                soli=ii;
                solj=jj;
            }
    fout<<minim+1<<" "<<soli<<" "<<solj<<" "<<"\n";
    return 0;
}