Pagini recente » Cod sursa (job #1789527) | Cod sursa (job #795165) | Cod sursa (job #2059835) | Cod sursa (job #2236329) | Cod sursa (job #1549590)
#include <fstream>
#include <queue>
#include <string>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
struct coord {
int lin;
int col;
};
char a[102][102];
char l1='\n';
int b[102][102],cc[102][102];
int main()
{
int n,i,j,m,mindrum=105,x,y;
coord P,Julieta,Romeo;
in>>n>>m;
noskipws(in);
for(i=1;i<=n;i++)
{
in>>l1;
for(j=1;j<=m;j++)
{
in>>a[i][j];
if(a[i][j]=='R')
{
Romeo.lin=i;
Romeo.col=j;
}
if(a[i][j]=='J')
{
Julieta.lin=i;
Julieta.col=j;
}
}
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]=='X')
b[i][j]=-1;
for(i=1;i<=n;i++)
{
b[i][0]=-1;
b[i][m+1]=-1;
}
for(i=1;i<=m;i++)
{
b[0][i]=-1;
b[n+1][i]=-1;
}
int l,c;
queue <coord> q;
q.push(Romeo);
b[0][0]=-1;
b[0][m+1]=-1;
b[n+1][0]=-1;
b[n+1][m+1]=-1;
b[Romeo.lin][Romeo.col]=1;
while(!q.empty())
{
l=q.front().lin;
c=q.front().col;
q.pop();
if(!b[l+1][c])
{
b[l+1][c]=b[l][c]+1;
P.lin=l+1;
P.col=c;
q.push(P);
}
if(!b[l+1][c-1])
{
b[l+1][c-1]=b[l][c]+1;
P.lin=l+1;
P.col=c-1;
q.push(P);
}
if(!b[l+1][c+1])
{
b[l+1][c+1]=b[l][c]+1;
P.lin=l+1;
P.col=c+1;
q.push(P);
}
if(!b[l][c-1])
{
b[l][c-1]=b[l][c]+1;
P.lin=l;
P.col=c-1;
q.push(P);
}
if(!b[l][c+1])
{
b[l][c+1]=b[l][c]+1;
P.lin=l;
P.col=c+1;
q.push(P);
}
if(!b[l-1][c])
{
b[l-1][c]=b[l][c]+1;
P.lin=l-1;
P.col=c;
q.push(P);
}
if(!b[l-1][c-1])
{
b[l-1][c-1]=b[l][c]+1;
P.lin=l-1;
P.col=c-1;
q.push(P);
}
if(!b[l-1][c+1])
{
b[l-1][c+1]=b[l][c]+1;
P.lin=l-1;
P.col=c+1;
q.push(P);
}
//<------------------------------------------------------------------------------------------------------------>
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]=='X')
cc[i][j]=-1;
for(i=1;i<=n;i++)
{
cc[i][0]=-1;
cc[i][m+1]=-1;
}
for(i=1;i<=m;i++)
{
cc[0][i]=-1;
cc[n+1][i]=-1;
}
cc[0][0]=-1;
cc[0][m+1]=-1;
cc[n+1][0]=-1;
cc[n+1][m+1]=-1;
cc[Julieta.lin][Julieta.col]=1;
queue <coord> Q;
Q.push(Julieta);
while(!Q.empty())
{
l=Q.front().lin;
c=Q.front().col;
Q.pop();
if(!cc[l+1][c])
{
cc[l+1][c]=cc[l][c]+1;
P.lin=l+1;
P.col=c;
Q.push(P);
}
if(!cc[l+1][c-1])
{
cc[l+1][c-1]=cc[l][c]+1;
P.lin=l+1;
P.col=c-1;
Q.push(P);
}
if(!cc[l+1][c+1])
{
cc[l+1][c+1]=cc[l][c]+1;
P.lin=l+1;
P.col=c+1;
Q.push(P);
}
if(!cc[l][c-1])
{
cc[l][c-1]=cc[l][c]+1;
P.lin=l;
P.col=c-1;
q.push(P);
}
if(!cc[l][c+1])
{
cc[l][c+1]=cc[l][c]+1;
P.lin=l;
P.col=c+1;
Q.push(P);
}
if(!cc[l-1][c])
{
cc[l-1][c]=cc[l][c]+1;
P.lin=l-1;
P.col=c;
Q.push(P);
}
if(!cc[l-1][c-1])
{
cc[l-1][c-1]=cc[l][c]+1;
P.lin=l-1;
P.col=c-1;
Q.push(P);
}
if(!cc[l-1][c+1])
{
cc[l-1][c+1]=cc[l][c]+1;
P.lin=l-1;
P.col=c+1;
Q.push(P);
}
}
//out<<cc[Romeo.lin][Romeo.col]<<' ';
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(b[i][j]==cc[i][j]&&b[i][j]!=-1&& b[i][j]!=0)
if(b[i][j]<mindrum)
{
mindrum=b[i][j];
x=i;
y=j;
}
}
out<<mindrum<<' '<<x<<' '<<y;
return 0;
}