Pagini recente » Cod sursa (job #2839050) | Cod sursa (job #2127739) | Cod sursa (job #309867) | Cod sursa (job #3291526) | Cod sursa (job #1155682)
#include<fstream>
#include<queue>
#define INF 9999999
using namespace std;
int dx[]={0, 1, 0, -1, 1, 1, -1, -1};
int dy[]={1, 0, -1, 0, 1, -1, 1, -1};
int **harta, n, m;
pair<int, int> Romeo, Julieta;
queue <pair<int,int> > q;
void BFS ()
{
harta[Romeo.first][Romeo.second]=1;
harta[Julieta.first][Julieta.second]=1;
ofstream g("rj.out");
pair<int, int> curent, new_curent;
q.push(Romeo);
while(!q.empty())
{
curent = q.front();
q.pop();
for(int i=0; i<8; i++)
{
new_curent.first = curent.first + dx[i];
new_curent.second = curent.second + dy[i];
if (harta[new_curent.first][new_curent.second]>harta[curent.first][curent.second])
{
harta[new_curent.first][new_curent.second] = harta[curent.first][curent.second] + 1;
q.push(new_curent);
}
}
}
q.push(Julieta);
while(!q.empty())
{
curent = q.front();
q.pop();
for(int i=0; i<8; i++)
{
new_curent.first = curent.first + dx[i];
new_curent.second = curent.second +dy[i];
if(harta[new_curent.first][new_curent.second] == harta [curent.first][curent.second] + 1)
{
g<<harta[new_curent.first][new_curent.second]<<" "<<new_curent.first<<" "<<new_curent.second;
return;
}
if(harta[new_curent.first][new_curent.second] > harta[curent.first][curent.second]
&& harta[new_curent.first][new_curent.second]!=INF)
{
harta[new_curent.first][new_curent.second] = harta[curent.first][curent.second] + 1;
q.push(new_curent);
}
}
}
}
int main()
{
string linie;
ifstream f("rj.in");
f>>n>>m;
harta = new int* [n+2];
for(int i=0; i<=n+1; i++)
harta[i]=new int [m+2];
getline(f, linie);
for(int i=1; i<=n; i++)
{
getline(f, linie);
for(int j=0; j<m; j++)
{
if(linie[j]==' ')
harta[i][j+1]=INF;
if(linie[j]=='X')
harta[i][j+1]=-1;
if(linie[j]=='R')
{
harta[i][j+1]=1;
Romeo.first=i;
Romeo.second=j+1;
}
if(linie[j]=='J')
{
harta[i][j+1]=1;
Julieta.first=i;
Julieta.second=j+1;
}
}
}
for(int i=0; i<=n+1; i++)
{
harta[i][0] = -1;
harta[i][m+1] = -1;
}
for(int i=0; i<=m+1; i++)
{
harta[0][i]=-1;
harta[m+1][i]=-1;
}
BFS();
return 0;
}