Pagini recente » Cod sursa (job #212487) | Cod sursa (job #1067501) | Cod sursa (job #751459) | Cod sursa (job #359328) | Cod sursa (job #2154515)
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
char a[100][100],s[100];
int i,j,n,m,startx[4],starty[4],x,y,i_urmator,j_urmator,p=1,ok;
queue<pair<int,int> >coada;
int di[]={0,-1,-1,-1,0,0,1,1,1};
int dj[]={0,-1,0,1,-1,1,-1,0,1};
struct
{
int nr,d;
}v[100][100];
bool OK(int i,int j)
{
if(i<1||j<1||i>n||j>m)
return false;
if(v[i][j].nr==-1)
return false;
return true;
}
int main()
{
f>>n>>m;int pi=n+1;int pj=m+1;int l=n*m+1;
for(i=1;i<=n;i++)
{
f.get();
f.get(s,100);
strcpy(a[i],s);
}
for(i=1;i<=n;i++)
{
for(j=0;j<m;j++)
{
if(a[i][j]==' ')
v[i][j+1].nr=n*m;
if(a[i][j]=='X')
v[i][j+1].nr=-1;
if(a[i][j]=='R'||a[i][j]=='J')
{
v[i][j+1].nr=1;
startx[p]=i;
starty[p]=j+1;
p++;
}
}
}
i=1;
coada.push(make_pair(startx[i],starty[i]));
while(!coada.empty())
{
x=coada.front().first;
y=coada.front().second;
v[x][y].d=1;
coada.pop();
for(int dir=1;dir<=8;dir++)
{
i_urmator=x+di[dir];
j_urmator=y+dj[dir];
if(OK(i_urmator,j_urmator)&&v[i_urmator][j_urmator].nr>v[x][y].nr+1)
{
v[i_urmator][j_urmator].nr=v[x][y].nr+1;
v[i_urmator][j_urmator].d=1;
coada.push(make_pair(i_urmator,j_urmator));
}
}}
i=2;
coada.push(make_pair(startx[i],starty[i]));
while(!coada.empty())
{
x=coada.front().first;
y=coada.front().second;
v[x][y].d=2;
coada.pop();
for(int dir=1;dir<=8;dir++)
{
i_urmator=x+di[dir];
j_urmator=y+dj[dir];
if(OK(i_urmator,j_urmator)&&v[i_urmator][j_urmator].nr>v[x][y].nr+1)
{
v[i_urmator][j_urmator].nr=v[x][y].nr+1;
v[i_urmator][j_urmator].d=2;
coada.push(make_pair(i_urmator,j_urmator));
}
else if(OK(i_urmator,j_urmator)&&v[i_urmator][j_urmator].nr==v[x][y].nr+1&&v[i_urmator][j_urmator].d!=v[x][y].d)
{
if(v[i_urmator][j_urmator].nr<l)
{
l=v[x][y].nr+1;
pi=i_urmator;
pj=j_urmator;
}
if(v[i_urmator][j_urmator].nr==l)
{
if(i_urmator<pi)
{
pi=i_urmator;
pj=j_urmator;
}
if(i_urmator==pi)
{
if(j_urmator<pj)
pj=j_urmator;
}
}
coada.push(make_pair(i_urmator,j_urmator));
}
}}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
g<<v[i][j].nr<<" ";
g<<"\n";
}
g<<l<<" "<<pi<<" "<<pj;
return 0;
}