Pagini recente » Cod sursa (job #82814) | Cod sursa (job #1666646) | Cod sursa (job #1066444) | Cod sursa (job #181198) | Cod sursa (job #885843)
Cod sursa(job #885843)
#include <fstream>
#include <vector>
#include <queue>
#include <limits>
const unsigned INF=std::numeric_limits<unsigned>::max()-2;
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; fin.ignore(10000,'\n');
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;}
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]){
if(costuriptR[i][j]<tmin){ tmin=costuriptR[i][j]; xmin=i; ymin=j; }
//else if(costuriptR[i][j]==tmin&&i<xmin){ xmin=i; ymin=j; }
}
fout<<tmin+1<<' '<<xmin+1<<' '<<ymin+1<<'\n';
}