Pagini recente » Borderou de evaluare (job #201112) | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #2435911) | Cod sursa (job #3224309) | Cod sursa (job #2515363)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
struct prec {
int x, y;
} mat[110][110];
int a[110][110],n,m,x[10010],y[10010],x1,x2,y1,y2,sf,i,j;
char s[110];
int solx[10010];
int soly[10010];
int soltotal;
void reconstituiretraseu(int lin, int col)
{
if(mat[lin][col].x == 0)
{
soltotal++;
solx[soltotal] = lin;
soly[soltotal] = col;
}
else
{
reconstituiretraseu(mat[lin][col].x, mat[lin][col].y);
soltotal++;
solx[soltotal] = lin;
soly[soltotal] = col;
}
}
int main()
{
in>>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)
{
in.get();
in.get(s,110);
for(j=0;j<m;++j)
{
if(s[j]=='X')
a[i][j+1]=-1;
if(s[j]=='R')
{
x1=i;
y1=j+1;
}
if(s[j]=='J')
{
x2=i;
y2=j+1;
}
s[j]=0;
}
}
x[1]=x1;
y[1]=y1;
sf=1;
for(i=1;x[i];++i)
{
int d1[]={0,0,1,1,1,-1,-1,-1},d2[]={1,-1,0,-1,1,1,0,-1};
for(j=0;j<8;++j)
{
if(a[x[i]+d1[j]][y[i]+d2[j]]==0)
{
a[x[i]+d1[j]][y[i]+d2[j]]=a[x[i]][y[i]]+1;
sf++;
x[sf]=x[i]+d1[j];
y[sf]=y[i]+d2[j];
int xnou = x[i] + d1[j];
int ynou = y[i] + d2[j];
if(mat[xnou][ynou].x != 0)
{
int xvechi = mat[xnou][ynou].x;
int yvechi = mat[xnou][ynou].y;
// (x[i], y[i]) -> xnou, you
// xvechi, yvechi -> xnou, ynou
if(xvechi > x[i] || (xvechi == x[i] && yvechi > y[i]))
{
mat[xnou][ynou].x = x[i];
mat[xnou][ynou].y = y[i];
}
}
else
{
mat[xnou][ynou].x = x[i];
mat[xnou][ynou].y = y[i];
}
}
}
}
mat[x1][y1].x = mat[x1][y1].y = 0;
a[x1][y1] = 0;
/*for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
out<<a[i][j]<<' ';
out<<'\n';
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
out << "( " << mat[i][j].x << ", " << mat[i][j].y << " ) ";
}
out << '\n';
}*/
reconstituiretraseu(x2, y2);
out<<(a[x2][y2]+1)/2+1<<' ';
if(soltotal%2==1)
out<<solx[soltotal/2+1]<<' '<<soly[soltotal/2+1];
else
{
if(solx[soltotal/2]<solx[soltotal/2+1])
{
out<<solx[soltotal/2]<<' '<<soly[soltotal/2];
return 0;
}
if(solx[soltotal/2]>solx[soltotal/2+1])
{
out<<solx[soltotal/2+1]<<' '<<soly[soltotal/2+1];
return 0;
}
if(soly[soltotal/2]<soly[soltotal/2+1])
{
out<<solx[soltotal/2]<<' '<<soly[soltotal/2];
return 0;
}
out<<solx[soltotal/2+1]<<' '<<soly[soltotal/2+1];
}
return 0;
}