Pagini recente » Cod sursa (job #2596951) | Monitorul de evaluare | Cod sursa (job #1536026) | Cod sursa (job #1520618) | Cod sursa (job #1170487)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int n,m;
char c[300];
queue<pair<int, int> > Q;
const int di[] = { 1, 0, -1, -1, -1, 0, 1,1 };
const int dj[] = { 1, 1, 1, 0, -1,-1,-1,0 };
int a[101][101];
int ro[101][101];
int ju[101][101];
bool inside(int i, int j)
{
return i<=n && j<=m && i>=1 && j >= 1;
}
int main()
{
fin>>n>>m;
fin.getline(c,30);
pair<int, int> romeo, julieta;
for(int i=1;i<=n;i++)
{
fin.getline(c,300);
for(int j=1;j<=m;j++)
if(c[j-1] == 'X')
{
a[i][j] = -1;
}
else if(c[j-1] == 'R')
{
romeo = make_pair(i,j);
}
else if(c[j-1] == 'J')
{
julieta = make_pair(i,j);
}
}
Q.push(romeo);
ro[romeo.first][romeo.second] = 1;
while(!Q.empty())
{
int i = Q.front().first;
int j = Q.front().second;
for(int k=0;k<8;k++)
{
int inou = i + di[k];
int jnou = j + dj[k];
if( !a[inou][jnou] && !ro[inou][jnou])
{
Q.push(make_pair(inou, jnou) );
ro[inou][jnou] = ro[i][j] + 1;
}
}
Q.pop();
}
Q.push(julieta);
ju[julieta.first][julieta.second] = 1;
while(!Q.empty())
{
int i = Q.front().first;
int j = Q.front().second;
for(int k=0;k<8;k++)
{
int inou = i + di[k];
int jnou = j + dj[k];
if( !a[inou][jnou] && !ju[inou][jnou])
{
Q.push(make_pair(inou, jnou) );
ju[inou][jnou] = ju[i][j] + 1;
}
}
Q.pop();
}
int val_min = 0x3f3f3f3f;
pair<int, int> sol;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(ro[i][j] == ju[i][j] && ro[i][j] && ro[i][j] < val_min)
{
sol = make_pair(i,j);
val_min = ro[i][j];
}
fout<<val_min<<' '<<sol.first<<' '<<sol.second;
fin.close();
return 0;
}