Pagini recente » Cod sursa (job #2382984) | Cod sursa (job #315501) | Cod sursa (job #890658) | Cod sursa (job #988640) | Cod sursa (job #625963)
Cod sursa(job #625963)
#include <iostream>
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
char map[105][105];
int N , M , sir[10] = {-1 , 0 , 1 , 0 , -1 , -1 , 1 , 1 , -1};
queue <pair <char , char> > Q;
bool viz[105][105];
int costR[105][105] , costJ[105][105];
void bfs (int x , int y , int dest1 , int dest2 , int cost[105][105])
{
int nod1 , nod2;
cost[x][y] = 1;
Q.push (make_pair (x , y));
while (!Q.empty ())
{
nod1 = Q.front ().first;
nod2 = Q.front ().second;
if (nod1 == dest1 && nod2 == dest2)
break;
for (int i = 1 ; i < 9 ; ++i)
{
if (viz[nod1 + sir[i]][nod2 + sir[i + 1]])
continue;
if (map[nod1 + sir[i]][nod2 + sir[i + 1]] == ' ')
{
viz[nod1 + sir[i]][nod2 + sir[i + 1]] = 1;
cost[nod1 + sir[i]][nod2 + sir[i + 1]] = cost[nod1][nod2] + 1;
Q.push (make_pair (nod1 + sir[i] , nod2 + sir[i + 1]));
}
}
Q.pop ();
}
}
int main ()
{
ifstream f ("rj.in");
ofstream g ("rj.out");
int cr1 , cr2 , cj1 , cj2;
f >> N >> M;
f.get ();
for (int i = 1 ; i <= N ; ++i)
{
f.getline (map[i] , 105);
for (int j = 0 ; j < M ; ++j)
{
if (map[i][j] == 'R')
{
cr1 = i;
cr2 = j;
}
else if (map[i][j] == 'J')
{
cj1 = i;
cj2 = j;
}
}
}
bfs (cr1 , cr2 , cj1 , cj2 , costR);
memset (viz , 0 , sizeof (viz));
bfs (cj1 , cj2 , cr1 , cr2 , costJ);
int minim = 99999 , ics , igrec;
for (int i = 1 ; i <= N ; ++i)
for (int j = 0 ; j < M ; ++j)
if (costR[i][j] == costJ[i][j] && costR[i][j] != 0 && costR[i][j] < minim)
{
minim = costR[i][j];
ics = i;
igrec = j + 1;
}
g << minim << " " << ics << " " << igrec;
return 0;
}