Pagini recente » Cod sursa (job #2484777) | Cod sursa (job #2739293) | Cod sursa (job #1727188) | Borderou de evaluare (job #1567337) | Cod sursa (job #3183216)
#include <iostream>
#include <queue>
#include <utility>
#include <fstream>
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
int n, m, ij, jj, ir, jr, traseuj[101][101], traseur[101][101], st[] = {0, 1, -1, 0, 0, 1, -1, -1, 1}, dr[] = {0, 0, 0, 1, -1, 1, -1, 1, -1};
char ma[101][101];
void citire()
{
fin >> n >> m;
fin.get();
for(int i = 1; i <= n; ++ i){
fin.getline(ma[i],101);
for(int j = 0; j < m; ++j)
{
char x;
x = ma[i][j];
if(x == ' ') traseur[i][j+1] = 0;
else
if(x == 'X') traseur[i][j+1] = -1;
else
if(x == 'R')
{
ir = i;
jr = j+1;
traseur[i][j+1] = 1;
}
else
{
ij = i;
jj = j+1;
traseuj[i][j+1] = 1;
traseur[i][j+1] = 1;
}
}
}
}
void afis()
{
traseur[ij][jj] = 0;
int minim = 999999, poz1, poz2;
for(int i = 1; i <= n; ++ i)
{
for(int j = 1; j <= m; ++j)
if(traseur[i][j] == traseuj[i][j] && traseuj[i][j] < minim && traseuj[i][j] != 0)
{
minim = traseuj[i][j];
poz1 = i;
poz2 = j;
}
}
fout << minim << ' ' << poz1 << ' ' << poz2;
}
void lee(int istart, int jstart)
{
queue<pair<int,int> > q;
traseuj[istart][jstart] = 1;
q.push(make_pair(istart,jstart));
while(!q.empty())
{
int p1 = q.front().first,p2 = q.front().second;
for(int j = 1; j <= 8; j++)
{
int iv = p1 + st[j], jv = p2 + dr[j];
if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && traseur[iv][jv] == 0 && traseuj[iv][jv] == 0)
{
traseuj[iv][jv] = traseuj[p1][p2] + 1;
q.push(make_pair(iv,jv));
}
}
q.pop();
}
}
void lee2(int istart, int jstart)
{
queue<pair<int,int> > c;
traseur[istart][jstart] = 1;
c.push(make_pair(istart,jstart));
while(!c.empty())
{
int p1 = c.front().first,p2 = c.front().second;
for(int j = 1; j <= 8; j++)
{
int iv = p1 + st[j], jv = p2 + dr[j];
//cout << iv << ' ' << jv << endl;
if(iv >= 1 && iv <= n && jv >= 1 && jv <= m && traseur[iv][jv] == 0)
{
traseur[iv][jv] = traseur[p1][p2] + 1;
c.push(make_pair(iv,jv));
}
}
c.pop();
}
}
int main()
{
citire();
lee(ij,jj);
lee2(ir,jr);
afis();
return 0;
}
/*
5 5
R XX
X X X
X XXX
X X X
X J X
*/