Pagini recente » Cod sursa (job #2061144) | Cod sursa (job #2821445) | Cod sursa (job #126212) | Cod sursa (job #1053117) | Cod sursa (job #2265733)
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
queue<pair<int, int> >q;
int rom[101][101]; // traseul lui romeo
int jul[101][101]; // traseul julietei
int linRomeo, colRomeo; // coordonatele lui Romeo
int linJulieta, colJulieta; // coordonatele Julietei
int di[] = {-1, -1, -1, 0, 1, 1, 1, 0}; // vector directie linie
int dj[] = {-1, 0, 1, 1, 1, 0, -1, -1}; // vector directie coloana
void border(int n, int m, int a[101][101]) // bordare matrice cu -1
{
for (int i = 0; i <= n+1; i++)
{
a[i][0] = -1;
a[i][m+1] = -1;
}
for (int j = 0; j <= m+1; j++)
{
a[0][j] = -1;
a[n+1][j] = -1;
}
}
void citire(int n, int m) //citire si creeare matrice romeo & julieta
{
for (int i = 1; i <= n; i++)
{
char x;
for (int j = 1; j <= m; j++)
{
f.get(x); if (x == 10) break;
if (x == ' ') {rom[i][j] = 0; jul[i][j] = 0;}
else if (x == 'X') {rom[i][j] = -1; jul[i][j] = -1;}
else if (x == 'R') {rom[i][j] = 0; jul[i][j] = 0; linRomeo = i; colRomeo = j;}
else if (x == 'J') {rom[i][j] = 0; jul[i][j] = 0; linJulieta = i; colJulieta = j;}
}
if (x != 10) f.get();
}
}
void leeRomeo()
{
int x = linRomeo;
int y = colRomeo;
rom[x][y] = 1;
q.push(make_pair(x, y));
while(!q.empty())
{
pair<int, int>p = q.front();
q.pop();
for (int k = 0; k < 8; k++)
{
if(rom[p.first+di[k]][p.second+dj[k]] == 0)
{
rom[p.first+di[k]][p.second+dj[k]] = 1 + rom[p.first][p.second];
q.push(make_pair(p.first+di[k], p.second+dj[k]));
}
}
}
}
void leeJulieta()
{
int x = linJulieta;
int y = colJulieta;
jul[x][y] = 1;
q.push(make_pair(x, y));
while(!q.empty())
{
pair<int, int>p = q.front();
q.pop();
for (int k = 0; k < 8; k++)
{
if(jul[p.first+di[k]][p.second+dj[k]] == 0)
{
jul[p.first+di[k]][p.second+dj[k]] = 1 + jul[p.first][p.second];
q.push(make_pair(p.first+di[k], p.second+dj[k]));
}
}
}
}
int main()
{
int n, m;
f >> n >> m; f.get();
citire(n, m);
border(n, m, rom);
border(n, m, jul);
leeRomeo();
leeJulieta();
int tmin = 200000, lin = 101, col = 101;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (rom[i][j] != -1 && rom[i][j] != 0)
if (rom[i][j] == jul[i][j])
if (rom[i][j] < tmin)
{
tmin = rom[i][j];
lin = i;
col = j;
}
g << tmin << ' ' << lin << ' ' << col;
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= m; j++)
// g << rom[i][j] << ' ';
// g << endl;
// }
// g << endl;
// for (int i = 1; i <= n; i++)
// {
// for (int j = 1; j <= m; j++)
// g << jul[i][j] << ' ';
// g << endl;
// }
// g << endl;
// g << linRomeo << ' ' << colRomeo << " " << linJulieta << ' ' << colJulieta;
return 0;
}