Pagini recente » Cod sursa (job #2502963) | Cod sursa (job #360862) | Cod sursa (job #2924108) | Cod sursa (job #361602) | Cod sursa (job #704140)
Cod sursa(job #704140)
#include<fstream>
#include<iostream>
#include<vector>
#include<cstdio>
//perle 2004
//spirala 2003
using namespace std;
char b[105];
vector <int> coada,coada1;
short a[105][105];
int romeo[105][105],julieta[105][105];
bool fol[105][105],fol1[105][105];
short x[10]={0,0,1,-1,1,1,-1,-1},y[10]={1,-1,0,0,1,-1,1,-1};
int n,m;
int xul,yul;
int drummin=9999999;
void cauta()
{
int xnou,ynou;
for(int i=0;i<coada.size();i+=2)
{
for(int d=0;d<=7;++d)
{
xnou=coada[i]+x[d];
ynou=coada[i+1]+y[d];
if((xnou>=1)&&(ynou>=1)&&(ynou<=m)&&(xnou<=n)&&(!a[xnou][ynou]))
{
if(!fol[xnou][ynou])
{
coada.push_back(xnou);
coada.push_back(ynou);
fol[xnou][ynou]=1;
}
else
{
if(romeo[xnou][ynou])
{
if(!romeo[coada[i]][coada[i+1]])
{
romeo[coada[i]][coada[i+1]]=romeo[xnou][ynou]+1;
}
else romeo[coada[i]][coada[i+1]]=min(romeo[coada[i]][coada[i+1]],romeo[xnou][ynou]+1);
}
}
}
}
}
}
void cauta1()
{
int xnou,ynou;
for(int i=0;i<coada1.size();i+=2)
{
for(int d=0;d<=7;++d)
{
xnou=coada1[i]+x[d];
ynou=coada1[i+1]+y[d];
if((xnou>=1)&&(ynou>=1)&&(ynou<=m)&&(xnou<=n)&&(!a[xnou][ynou]))
{
if(!fol1[xnou][ynou])
{
coada1.push_back(xnou);
coada1.push_back(ynou);
fol1[xnou][ynou]=1;
}
else
{
if(julieta[xnou][ynou])
{
if(!julieta[coada1[i]][coada1[i+1]])
{
julieta[coada1[i]][coada1[i+1]]=julieta[xnou][ynou]+1;
}
else julieta[coada1[i]][coada1[i+1]]=min(julieta[coada1[i]][coada1[i+1]],julieta[xnou][ynou]+1);
}
}
}
}
if(romeo[coada1[i]][coada1[i+1]]==julieta[coada1[i]][coada1[i+1]])
{
if(drummin>romeo[coada1[i]][coada1[i+1]])
{
drummin=romeo[coada1[i]][coada1[i+1]];
xul=coada1[i];
yul=coada1[i+1];
}
else if(drummin==romeo[coada1[i]][coada1[i+1]])
{
if(xul>coada1[i])
{
xul=coada1[i];
yul=coada1[i+1];
}
else if(xul==coada1[i])
{
if(yul>coada1[i])
{
xul=coada1[i];
yul=coada1[i+1];
}
}
}
}
}
}
int main()
{
ifstream f1("rj.in");
ofstream f2("rj.out");
f1>>n>>m;
for(int i=0;i<=n;++i)
{
f1.getline(b,101);
for(int d=0;d<strlen(b);++d)
{
if(b[d]=='X')
{
a[i][d+1]=1;
}
else if(b[d]=='R')
{
coada.push_back(i);
coada.push_back(d+1);
fol[i][d+1]=1;
romeo[i][d+1]=1;
}
else if(b[d]=='J')
{
coada1.push_back(i);
coada1.push_back(d+1);
fol1[i][d+1]=1;
julieta[i][d+1]=1;
}
}
}
cauta();
cauta1();
f2<<drummin<<" "<<xul<<" "<<yul<<" ";
//for(int i=1;i<=n;++i)
//{
// for(int d=1;d<=m;++d)
// {
// f2<<romeo[i][d]<<" ";
// }
// f2<<'\n';
//}
//f2<<'\n';
//f2<<'\n';
//for(int i=1;i<=n;++i)
//{
// for(int d=1;d<=m;++d)
// {
// f2<<julieta[i][d]<<" ";
//}
// f2<<'\n';
// }
//
return 0;
}