Pagini recente » Cod sursa (job #1553133) | Cod sursa (job #1464023) | Cod sursa (job #981711) | Cod sursa (job #263537) | Cod sursa (job #2482055)
#include <queue>
#include <fstream>
#include <cstring>
#include <utility>
#include <iostream>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int r[105][105], jul[105][105], n, m, cn, ln, lc, cc;
int tmin=1e9+1;
char s[105];
int dx[]={-1, -1, 0, 1, 1, 1, 0, -1};
int dy[]={0, 1, 1, 1, 0, -1, -1, -1};
struct p{
int x, y;
}start1, start2, pnou;
queue < pair <int, int> > q;
void bordare()
{ for (int i=0;i<=n+1;i++) r[i][0]=jul[i][0]=r[i][n+1]=jul[i][n+1]=-1;
for (int i=0;i<=m+1;i++) r[0][i]=jul[0][i]=r[m+1][i]=jul[m+1][i]=-1;
}
void citire()
{ f>>n>>m;
f.get();
for (int i=1;i<=n;i++)
{ f.getline(s, 105);
for (int j=0;j<m;j++)
{ if (s[j]=='X') r[i][j+1]=jul[i][j+1]=-1;
else if (s[j]==' ') r[i][j+1]=jul[i][j+1]=0;
else if (s[j]=='R')
{ start1.x=i;
start1.y=j+1;
}
else if (s[j]=='J')
{ start2.x=i;
start2.y=j+1;
}
}
}
bordare();
}
bool okR(int l, int c)
{
return l>0 && l<n+1 && c>0 && c<m+1 && r[l][c]==0;
}
bool okJ(int l, int c)
{
return l>0 && l<n+1 && c>0 && c<m+1 && jul[l][c]==0;
}
void leeR()
{
r[start1.x][start1.y]=1;
q.push(make_pair(start1.x,start1.y));
while (!q.empty())
{ lc=q.front().first;
cc=q.front().second;
q.pop();
for (int k=0;k<8;k++)
{ ln=lc+dx[k];
cn=cc+dy[k];
if (okR (ln, cn)==1 )
{ r[ln][cn]=r[lc][cc]+1;
q.push(make_pair(ln,cn));
}
}
}
}
void leeJ()
{
jul[start2.x][start2.y]=1;
q.push(make_pair(start2.x, start2.y));
while (!q.empty())
{ lc=q.front().first;
cc=q.front().second;;
q.pop();
for (int k=0;k<8;k++)
{ ln=lc+dx[k];
cn=cc+dy[k];
if (okJ (ln, cn)==1 )
{ jul[ln][cn]=jul[lc][cc]+1;
q.push(make_pair(ln,cn));
}
}
}
}
void afisare()
{
int linie, coloana;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{ if (r[i][j]==jul[i][j] && tmin>r[i][j] && r[i][j]>0)
{ tmin=r[i][j];
linie=i;
coloana=j;
}
}
g<<tmin<<" "<<linie<<" "<<coloana<<'\n';
}
int main()
{
citire();
leeR();
leeJ();
afisare();
return 0;
}