Pagini recente » Cod sursa (job #2741279) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #235064) | Cod sursa (job #1180554)
#include <iostream>
#include <fstream>
#include <queue>
#define Nmax 250
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
short int colmin=200;minn=9999,q,t,i,j1,n,m,a[Nmax][Nmax],b[Nmax][Nmax],ro[Nmax][Nmax],ju[Nmax][Nmax];
struct punct {int x,y;};
punct rom,jul;
void reading(short int &n,short int &m)
{
char c[250];
int k,j;
f>>n>>m;
f.getline(c,250);
for(k=1;k<=n;++k)
{
f.getline(c,250);
for(j=0;j<=m-1;++j)
{
if (c[j]=='X') a[k][j+1]=b[k][j+1]=1;
else if (c[j]==' ') a[k][j+1]=b[k][j+1]=0;
else if (c[j]=='R') {a[k][j+1]=b[k][j+1]=0;rom.x=k;rom.y=j+1;}
else {a[k][j+1]=b[k][j+1]=0;jul.x=k;jul.y=j+1;}
ro[k][j+1]=ju[k][j+1]=0;
}
}
f.close();
}
void leer()
{
deque<short int>d;
d.push_front(rom.y);
d.push_front(rom.x);
a[rom.y][rom.x]=1;
while(!d.empty())
{
short int xx,yy;
xx=d.front();d.pop_front();
yy=d.front();d.pop_front();
if (xx>1) if (!a[xx-1][yy])
{
if (!ro[xx-1][yy])
{
ro[xx-1][yy]=ro[xx][yy]+1;
a[xx-1][yy]=1;
d.push_back(xx-1);
d.push_back(yy);
}
}
if (xx<n) if (!a[xx+1][yy])
{
if (!ro[xx+1][yy])
{
ro[xx+1][yy]=ro[xx][yy]+1;
a[xx+1][yy]=1;
d.push_back(xx+1);
d.push_back(yy);
}
}
if (yy>1) if (!a[xx][yy-1])
{
if (!ro[xx][yy-1])
{
ro[xx][yy-1]=ro[xx][yy]+1;
a[xx][yy-1]=1;
d.push_back(xx);
d.push_back(yy-1);
}
}
if (yy<m) if (!a[xx][yy+1])
{
if (!ro[xx][yy+1])
{
ro[xx][yy+1]=ro[xx][yy]+1;
a[xx][yy+1]=1;
d.push_back(xx);
d.push_back(yy+1);
}
}
if (xx<n) if (yy<m) if (!a[xx+1][yy+1])
{
if (!ro[xx+1][yy+1])
{
ro[xx+1][yy+1]=ro[xx][yy]+1;
a[xx+1][yy+1]=1;
d.push_back(xx+1);
d.push_back(yy+1);
}
}
if (xx>1) if (yy>1) if (!a[xx-1][yy-1])
{
if (!ro[xx-1][yy-1])
{
ro[xx-1][yy-1]=ro[xx][yy]+1;
a[xx-1][yy-1]=1;
d.push_back(xx-1);
d.push_back(yy-1);
}
}
if (xx<n) if (yy>1) if (!a[xx+1][yy-1])
{
if (!ro[xx+1][yy-1])
{
ro[xx+1][yy-1]=ro[xx][yy]+1;
a[xx+1][yy-1]=1;
d.push_back(xx+1);
d.push_back(yy-1);
}
}
if (xx>1) if (yy<m) if (!a[xx-1][yy+1])
{
if (!ro[xx-1][yy+1])
{
ro[xx-1][yy+1]=ro[xx][yy]+1;
a[xx-1][yy+1]=1;
d.push_back(xx-1);
d.push_back(yy+1);
}
}
}
}
void leej()
{
deque<short int>d;
d.push_front(jul.y);
d.push_front(jul.x);
b[jul.x][jul.y]=1;
while(!d.empty())
{
short int xx,yy;
xx=d.front();d.pop_front();
yy=d.front();d.pop_front();
if (xx>1) if (!b[xx-1][yy])
{
if (!ju[xx-1][yy])
{
ju[xx-1][yy]=ju[xx][yy]+1;
b[xx-1][yy]=1;
d.push_back(xx-1);
d.push_back(yy);
}
}
if (xx<n) if (!b[xx+1][yy])
{
if (!ju[xx+1][yy])
{
ju[xx+1][yy]=ju[xx][yy]+1;
b[xx+1][yy]=1;
d.push_back(xx+1);
d.push_back(yy);
}
}
if (yy>1) if (!b[xx][yy-1])
{
if (!ju[xx][yy-1])
{
ju[xx][yy-1]=ju[xx][yy]+1;
b[xx][yy-1]=1;
d.push_back(xx);
d.push_back(yy-1);
}
}
if (yy<m) if (!b[xx][yy+1])
{
if (!ju[xx][yy+1])
{
ju[xx][yy+1]=ju[xx][yy]+1;
b[xx][yy+1]=1;
d.push_back(xx);
d.push_back(yy+1);
}
}
if (xx<n) if (yy<m) if (!b[xx+1][yy+1])
{
if (!ju[xx+1][yy+1])
{
ju[xx+1][yy+1]=ju[xx][yy]+1;
b[xx+1][yy+1]=1;
d.push_back(xx+1);
d.push_back(yy+1);
}
}
if (xx>1) if (yy>1) if (!b[xx-1][yy-1])
{
if (!ju[xx-1][yy-1])
{
ju[xx-1][yy-1]=ju[xx][yy]+1;
b[xx-1][yy-1]=1;
d.push_back(xx-1);
d.push_back(yy-1);
}
}
if (xx<n) if (yy>1) if (!b[xx+1][yy-1])
{
if (!ju[xx+1][yy-1])
{
ju[xx+1][yy-1]=ju[xx][yy]+1;
b[xx+1][yy-1]=1;
d.push_back(xx+1);
d.push_back(yy-1);
}
}
if (xx>1) if (yy<m) if (!b[xx-1][yy+1])
{
if (!ju[xx-1][yy+1])
{
ju[xx-1][yy+1]=ju[xx][yy]+1;
b[xx-1][yy+1]=1;
d.push_back(xx-1);
d.push_back(yy+1);
}
}
}
}
int main()
{
reading(n,m);
leer();
leej();
for(i=1;i<=n;++i)
{
for(j1=1;j1<=m;++j1)
if ((ro[i][j1]>0) && (ro[i][j1]==ju[i][j1]) && (ro[i][j1]<=minn))
{
if (ro[i][j1]==minn && j1<colmin)
{
minn=ro[i][j1];
q=i;t=j1;
colmin=j1;
}
else if (ro[i][j1]<minn)
{
minn=ro[i][j];
q=i;t=j1;
colmin=j1;
}
}
}
g<<minn+1<<" "<<q<<" "<<t;
g.close();
return 0;
}