Pagini recente » Cod sursa (job #1995013) | Cod sursa (job #2984317) | Cod sursa (job #2891170) | Cod sursa (job #811706) | Cod sursa (job #2658558)
#include <fstream>
#include <deque>
#include <vector>
#include <string>
#include <climits>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
const int moveRow[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int moveCol[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int R, C;
int rowR, colR;
int rowJ, colJ;
vector < vector <int> > romeo;
vector < vector <int> > julieta;
void bord(vector < vector <int> > &grid){
for(int row = 0; row <= R + 1; ++row)
grid[row][0] = grid[row][C + 1] = -1;
for(int col = 0; col <= C + 1; ++col)
grid[0][col] = grid[R + 1][col] = -1;
}
void BFS(const int &startRow, const int &startCol, vector < vector <int> > &grid){
deque < pair <int, int> > Queue;
Queue.push_back({startRow, startCol});
grid[startRow][startCol] = 1;
while(!Queue.empty()){
pair <int, int> Cell = Queue.front();
Queue.pop_front();
int row = Cell.first;
int col = Cell.second;
for(int dir = 0; dir < 8; ++dir){
int newRow = row + moveRow[dir];
int newCol = col + moveCol[dir];
if(grid[newRow][newCol] == 0){
Queue.push_back({newRow, newCol});
grid[newRow][newCol] = grid[row][col] + 1;
}
}
}
}
int main(){
fin >> R >> C;
romeo = vector < vector <int> >(R + 2, vector <int> (C + 2));
julieta = vector < vector <int> >(R + 2, vector <int> (C + 2));
string line;
getline(fin, line);
for(int row = 1; row <= R; ++row){
getline(fin, line);
for(int col = 0; col < C; ++col)
if(line[col] == 'X')
romeo[row][col + 1] = julieta[row][col + 1] = -1;
else if(line[col] == 'R')
rowR = row, colR = col + 1;
else if(line[col] == 'J')
rowJ = row, colJ = col + 1;
}
bord(romeo);
bord(julieta);
BFS(rowR, colR, romeo);
BFS(rowJ, colJ, julieta);
int tmin = INT_MAX;
int ansRow = -1;
int ansCol = -1;
for(int row = 1; row <= R; ++row)
for(int col = 1; col <= C; ++col)
if(romeo[row][col] > 0 and julieta[row][col] > 0)
if(max(romeo[row][col], julieta[row][col]) < tmin){
tmin = max(romeo[row][col], julieta[row][col]);
ansRow = row;
ansCol = col;
}
fout << tmin << ' ' << ansRow << ' ' << ansCol << '\n';
}