Cod sursa(job #885812)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 22 februarie 2013 13:05:51
Problema Rj Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <fstream>
#include <vector>
#include <queue>
#include <limits>

const unsigned INF=std::numeric_limits<unsigned>::max();

struct COORD{
    unsigned x; unsigned y;
    COORD(unsigned a, unsigned b){x=a;y=b;}
    COORD(){x=0;y=0;}
};

void Lee(std::vector<std::vector<unsigned> > &costs,COORD start,const std::vector<std::vector<char> > &matr){
    std::queue<COORD> sor;
    sor.push(start); costs[start.x][start.y]=0;
    while(!sor.empty()){
        unsigned i=sor.front().x, j=sor.front().y;
        //vizsz,fugg
        if(i!=0&&matr[i-1][j]==' '&&costs[i-1][j]>costs[i][j]+1){
            costs[i-1][j]=costs[i][j]+1;
            sor.push(COORD(i-1,j));
        }
        if(i!=matr.size()-1&&matr[i+1][j]==' '&&costs[i+1][j]>costs[i][j]+1){
            costs[i+1][j]=costs[i][j]+1;
            sor.push(COORD(i+1,j));
        }
        if(j!=0&&matr[i][j-1]==' '&&costs[i][j-1]>costs[i][j]+1){
            costs[i][j-1]=costs[i][j]+1;
            sor.push(COORD(i,j-1));
        }
        if(j!=matr[0].size()-1&&matr[i][j+1]==' '&&costs[i][j+1]>costs[i][j]+1){
            costs[i][j+1]=costs[i][j]+1;
            sor.push(COORD(i,j+1));
        }
        //atlos...
        if(i!=0&&j!=0&&matr[i-1][j-1]==' '&&costs[i-1][j-1]>costs[i][j]+1){
            costs[i-1][j-1]=costs[i][j]+1;
            sor.push(COORD(i-1,j-1));
        }
        if(i!=0&&j!=matr[0].size()-1&&matr[i-1][j+1]==' '&&costs[i-1][j+1]>costs[i][j]+1){
            costs[i-1][j+1]=costs[i][j]+1;
            sor.push(COORD(i-1,j+1));
        }
        if(i!=matr.size()-1&&j!=0&&matr[i+1][j-1]==' '&&costs[i+1][j-1]>costs[i][j]+1){
            costs[i+1][j-1]=costs[i][j]+1;
            sor.push(COORD(i+1,j-1));
        }
        if(i!=matr.size()-1&&j!=matr[0].size()-1&&matr[i+1][j+1]==' '&&costs[i+1][j+1]>costs[i][j]+1){
            costs[i+1][j+1]=costs[i][j]+1;
            sor.push(COORD(i+1,j+1));
        }
        sor.pop();
    }
}

int main(){
    std::ifstream fin("rj.in");
    std::ofstream fout("rj.out");

    unsigned n,m; fin>>n>>m;
    std::vector<std::vector<char> > matr(n,std::vector<char>(m));

    COORD R,J;
    std::vector<std::vector<unsigned> > costuriptR(n,std::vector<unsigned>(m,INF));
    std::vector<std::vector<unsigned> > costuriptJ(n,std::vector<unsigned>(m,INF));

    for(unsigned i=0;i<n;++i){
        for(unsigned j=0;j<m;++j){
            fin.get(matr[i][j]);
            if(matr[i][j]=='R'){matr[i][j]='X';R.x=i;R.y=j;}
            else if(matr[i][j]=='J'){matr[i][j]='X';J.x=i;J.y=j;}
        }
        fin.ignore(10000,'\n');
    }

    Lee(costuriptR,R,matr);
    Lee(costuriptJ,J,matr);

    unsigned tmin=INF,xmin=0,ymin=0;
    for(unsigned i=0;i<n;++i)
        for(unsigned j=0;j<m;++j)
            if(matr[i][j]!='X'&&costuriptR[i][j]==costuriptJ[i][j]&&costuriptR[i][j]<tmin){
                tmin=costuriptR[i][j]; xmin=i; ymin=j;
            }

    fout<<tmin+1<<' '<<xmin+1<<' '<<ymin+1<<'\n';
}