Pagini recente » Cod sursa (job #734523) | Simulare 11 | Cod sursa (job #2386708) | Cod sursa (job #1513726) | Cod sursa (job #2423660)
#include <iostream>
#include <fstream>
#include <queue>
int** BFS(int** mat, int n, int m, int x, int y)
{
int** dist = new int* [n];
for(int i = 0; i < m; i++)
{
dist[i] = new int[m];
std::fill_n(dist[i], m, -1);
}
std::queue<int> queue;
queue.push(y * m + x);
dist[y][x] = 1;
while(!queue.empty())
{
int x = queue.front();
int u = x / m;
int v = x % m;
for(int r = -1; r <= 1; r++)
{
if(u + r < 0 || u + r >= n)
continue;
for(int c = -1; c <= 1; c++)
{
if((c == 0 && r == 0) || v + c < 0 || v + c >= m)
continue;
if(dist[u + r][v + c] < 0 && mat[u + r][v + c])
{
dist[u + r][v + c] = dist[u][v] + 1;
queue.push((u + r) * m + (v + c));
}
}
}
queue.pop();
}
return dist;
}
int main()
{
std::ifstream fin("rj.in");
std::ofstream fout("rj.out");
if(!fin.is_open() || !fout.is_open())
return;
int n = 0, m = 0, r_x = 0, r_y = 0, j_x = 0, j_y = 0;
char ch = 0;
int** mat = nullptr;
int** dist_rom = nullptr;
int** dist_jul = nullptr;
fin >> n >> m;
fin >> std::noskipws >> ch;
mat = new int* [n];
for(int i = 0; i < n; i++)
{
mat[i] = new int[m];
for(int j = 0; j < m; j++)
{
fin >> std::noskipws >> ch;
switch(ch)
{
case 'R':
mat[i][j] = 1;
r_x = j;
r_y = i;
break;
case 'J':
mat[i][j] = 1;
j_x = j;
j_y = i;
break;
case 'X':
mat[i][j] = 0;
break;
default:
mat[i][j] = 1;
break;
}
}
fin >> std::noskipws >> ch;
}
dist_rom = BFS(mat, n, m, r_x, r_y);
dist_jul = BFS(mat, n, m, j_x, j_y);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(dist_rom[i][j] > 0 && dist_rom[i][j] == dist_jul[i][j])
{
fout << dist_rom[i][j] << ' ' << i + 1 << ' ' << j + 1;
i = n;
j = m;
}
}
}
for(int i = 0; i < n; i++)
{
delete[] mat[i];
delete[] dist_rom[i];
delete[] dist_jul[i];
}
delete[] mat;
delete[] dist_rom;
delete[] dist_jul;
return 0;
}