Pagini recente » Cod sursa (job #941364) | Cod sursa (job #3246579) | Cod sursa (job #2947740) | Cod sursa (job #607340) | Cod sursa (job #1158814)
#include<fstream>
#include<queue>
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, **harta1, n, m;
pair<int, int> Romeo, Julieta;
queue <pair<int,int> > q;
void BFS ()
{
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] ==0)
{
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(harta1[new_curent.first][new_curent.second] == 0)
{
harta1[new_curent.first][new_curent.second] = harta1[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];
harta1= new int* [n+2];
for(int i=0; i<=n+1; i++)
{
harta[i]= new int [m+2];
harta1[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] = 0;
harta1[i][j+1]= 0;
}
if(linie[j]=='X')
{
harta[i][j+1] = -1;
harta1[i][j+1]= -1;
}
if(linie[j]=='R')
{
harta[i][j+1]=1;
harta1[i][j+1]=0;
Romeo.first=i;
Romeo.second=j+1;
}
if(linie[j]=='J')
{
harta1[i][j+1]=1;
harta[i][j+1]=0;
Julieta.first=i;
Julieta.second=j+1;
}
}
}
for(int i=0; i<=n+1; i++)
{
harta[i][0] = -1;
harta[i][m+1] = -1;
harta1[i][0] = -1;
harta1[i][m+1] = -1;
}
for(int i=0; i<=m+1; i++)
{
harta[0][i] = -1;
harta[n+1][i]=-1;
harta1[0][i]=-1;
harta1[n+1][i]=-1;
}
BFS();
int minn = 0;
pair <int, int> coord;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
if (harta[i][j] == harta1[i][j] && harta[i][j]!=0 && harta[i][j]!=-1)
{
if(minn == 0)
{
minn=harta[i][j];
coord = make_pair(i, j);
}
if(minn>harta[i][j])
{
minn = harta[i][j];
coord = make_pair(i, j);
}
}
ofstream g("rj.out");
g<<minn<<" "<<coord.first<<" "<<coord.second;
f.close();
g.close();
return 0;
}