Pagini recente » Cod sursa (job #2487085) | Cod sursa (job #2859144) | Cod sursa (job #1347980) | Cod sursa (job #2767724) | Cod sursa (job #1611693)
#include <fstream>
#include <queue>
#include <bitset>
#include <cstring>
#define Nmax 109
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
#define x first
#define y second
typedef pair <int,int> point;
int n,m,jul[Nmax][Nmax],rom[Nmax][Nmax],a[Nmax][Nmax],nr,cnt;
int dx[10]={8,-1,-1,0,1,1,1,0,-1};
int dy[10]={8,0,1,1,1,0,-1,-1,-1};
string c;
point romeo,julieta,sol;
queue <point> Q;
bitset <Nmax> inQ[Nmax];
void RomLee(int sx, int sy)
{
rom[sx][sy]=1;
Q.push(point(sx,sy));
inQ[sx][sy]=1;
while (!Q.empty())
{
point curent=Q.front();
Q.pop();
int x=curent.x;
int y=curent.y;
inQ[x][y]=0;
for (int k=1; k<=8; ++k)
{
int p=x+dx[k];
int q=y+dy[k];
if (p>=1 && p<=n && q>=1 && q<=m && a[p][q]==0 && (rom[p][q]==0 || rom[p][q]>rom[x][y]+1))
{
rom[p][q]=rom[x][y]+1;
if (!inQ[p][q])
{
Q.push(point(p,q));
inQ[p][q]=1;
}
}
}
}
}
void JulLee(int sx, int sy)
{
jul[sx][sy]=1;
Q.push(point(sx,sy));
inQ[sx][sy]=1;
while (!Q.empty())
{
point curent=Q.front();
Q.pop();
int x=curent.x;
int y=curent.y;
inQ[x][y]=0;
for (int k=1; k<=8; ++k)
{
int p=x+dx[k];
int q=y+dy[k];
if (p>=1 && p<=n && q>=1 && q<=m && a[p][q]==0 && (jul[p][q]==0 || jul[p][q]>jul[x][y]+1))
{
jul[p][q]=jul[x][y]+1;
if (!inQ[p][q])
{
Q.push(point(p,q));
inQ[p][q]=1;
}
}
}
}
}
int main()
{
f>>n>>m;
for (int i=1; i<=n+1; ++i)
{
getline(f,c);
// g<<c<<'\n';
for (int j=1; j<=m; ++j)
{
if (c[j-1]=='R') romeo=point(i-1,j);
if (c[j-1]=='J') julieta=point(i-1,j);
if (c[j-1]=='X') a[i-1][j]=1;
}
}
RomLee(romeo.x,romeo.y);
JulLee(julieta.x,julieta.y);
/* for (int i=1; i<=n; ++i)
{
for (int j=1; j<=m; ++j) g<<a[i][j];
g<<'\n';
}
g<<'\n';
for (int i=1; i<=n; ++i)
{
for (int j=1; j<=m; ++j) g<<rom[i][j]<<' ';
g<<'\n';
}
g<<'\n';
for (int i=1; i<=n; ++i)
{
for (int j=1; j<=m; ++j) g<<jul[i][j]<<' ';
g<<'\n';
}
g<<'\n';
g<<romeo.x<<' '<<romeo.y<<'\n';
g<<julieta.x<<' '<<julieta.y<<'\n';*/
int minn=100000;
for (int i=1; i<=n; ++i)
for (int j=1; j<=m; ++j)
if (rom[i][j]==jul[i][j] && rom[i][j]<minn && rom[i][j]!=0)
{
minn=rom[i][j];
sol=point(i,j);
}
g<<minn<<' '<<sol.x<<' '<<sol.y<<'\n';
f.close();
g.close();
return 0;
}