Pagini recente » Cod sursa (job #1422678) | Cod sursa (job #1503597) | Cod sursa (job #3000728) | Cod sursa (job #2612123) | Cod sursa (job #2424441)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
struct punct{
int x,y;
};
ifstream f("rj.in");
ofstream g("rj.out");
int n,m;
int OffsetI[8] = {0,0,1,-1,1,-1,1,-1};
int OffsetJ[8] = {1,-1,0,0,1,-1,-1,1};
punct R, J;
queue <punct> MyQueue;
bool OK(int i, int j)
{
int n2 = n;n2--;
int m2 = m;m2--;
if (i > n || i < 1)return 0;
if (j > m || j < 1)return 0;
return 1;
}
void BFS(vector<vector<int>>&matrice, punct Start)
{
punct Aux;
MyQueue.push(Start);
while(!MyQueue.empty())
{
Aux = MyQueue.front();
MyQueue.pop();
for(int i=0;i<8;i++)
{
punct node;
node.x = Aux.x + OffsetI[i];
node.y = Aux.y + OffsetJ[i];
if(OK(node.x, node.y) == true && matrice[node.x][node.y] == 0)
{
matrice[node.x][node.y] = matrice[Aux.x][Aux.y] + 1;
MyQueue.push(node);
}
}
}
}
int main()
{
f >> n >> m;
vector<vector<char>>mapa(n+1, vector<char>(m+1));
vector<vector<int>>RomeoMap(n+1, vector<int>(m+1));
vector<vector<int>>JulieMap(n+1, vector<int>(m+1));
f.get();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f.get(mapa[i][j]);
if(mapa[i][j] == 'R')
{
R.x = i;
R.y = j;
RomeoMap[i][j] = 1;
JulieMap[i][j] = 0;
}
else if(mapa[i][j] == 'J')
{
J.x = i;
J.y = j;
JulieMap[i][j] = 1;
RomeoMap[i][j] = 0;
}
else if(mapa[i][j] == 'X')
{
RomeoMap[i][j] = -1;
JulieMap[i][j] = -1;
}
else
{
RomeoMap[i][j] = 0;
JulieMap[i][j] = 0;
}
}
f.get();
}
BFS(RomeoMap, R);
BFS(JulieMap, J);
punct Sol;
int minim = INT32_MAX;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(RomeoMap[i][j] == JulieMap[i][j] && RomeoMap[i][j] < minim && RomeoMap[i][j] > 0)
{
minim = RomeoMap[i][j];
Sol.x = i;
Sol.y = j;
}
}
}
g << minim << " " << Sol.x << " " << Sol.y;
return 0;
}