Pagini recente » Cod sursa (job #2431629) | Cod sursa (job #2269757) | Cod sursa (job #2330813) | Cod sursa (job #2153767) | Cod sursa (job #2586068)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m,rlin,rcol,jlin,jcol;
char ch[205];
short a[105][105],b[105][105],c[105][105];
short dx[]={0,0,-1,-1,-1,1,1,1};
short dy[]={-1,1,0,-1,1,0,-1,1};
struct poz
{
int x;
int y;
};
queue<poz> q;
void Bordare()
{
for(int i=0;i<=m+1;i++)
{
a[0][i]=a[n+1][i]=1;
}
for(int i=0;i<=n+1;i++)
{
a[i][0]=a[i][m+1]=1;
}
}
void Citire()
{
fin>>n>>m;
fin.getline(ch,200);
for(int i=1;i<=n;i++)
{
fin.getline(ch,200);
for(int j=0;j<=m;j++)
{
if(ch[j]=='X')
{
a[i][j+1]=1;
}
else if(ch[j]=='R')
{
rlin=i;
rcol=j+1;
}
else if(ch[j]=='J')
{
jlin=i;
jcol=j;
}
}
}
}
void Lee1(int xx,int yy)
{
poz w1,w2;
w1.x=xx;
w1.y=yy;
b[xx][yy]=1;
while(!q.empty())
{
q.pop();
}
q.push(w1);
while(!q.empty())
{
w1=q.front();
q.pop();
int x=w1.x,y=w1.y;
for(int k=0;k<=7;k++)
{
int i=x+dx[k],j=y+dy[k];
if(a[i][j]==0&&(b[i][j]==0||b[i][j]>b[x][y]+1))
{
b[i][j]=b[x][y]+1;
w2.x=i;
w2.y=j;
q.push(w2);
}
}
}
}
void Lee2(int xx,int yy)
{
poz w1,w2;
w1.x=xx;
w1.y=yy;
c[xx][yy]=1;
while(!q.empty())
{
q.pop();
}
q.push(w1);
while(!q.empty())
{
w1=q.front();
q.pop();
int x=w1.x,y=w1.y;
for(int k=0;k<=7;k++)
{
int i=x+dx[k],j=y+dy[k];
if(a[i][j]==0&&(c[i][j]==0||c[i][j]>c[x][y]+1))
{
c[i][j]=c[x][y]+1;
w2.x=i;
w2.y=j;
q.push(w2);
}
}
}
}
void Rezolvare()
{
int minim=10000,lmin,cmin;
Lee1(rlin,rcol);
Lee2(jlin,jcol);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(b[i][j]!=0&&b[i][j]==c[i][j]&&b[i][j]<minim)
{
minim=b[i][j];
lmin=i;
cmin=j;
}
}
}
fout<<minim<<" "<<lmin<<" "<<cmin<<" ";;
}
int main()
{
Citire();
Bordare();
Rezolvare();
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<b[i][j]<<" ";
}
cout<<"\n";
}
cout<<"-------------------------------------\n";
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<c[i][j]<<" ";
}
cout<<"\n";
}*/
return 0;
}