Pagini recente » Borderou de evaluare (job #2334904) | Borderou de evaluare (job #2301288) | Cod sursa (job #2477767)
#include <fstream>
#include <queue> // std::queue
#include <utility> // std::pair
const unsigned nr_dirs = 8;
const int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 },
dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
unsigned N, M; // 1 < N, M < 101
int A[103][103], B[103][103];
struct Position
{
int lin, col;
} Rom, Jul;
inline void border()
{
for (unsigned i = 0; i <= N + 1; ++i)
{
A[i][0] = A[i][M + 1] = B[i][0] = B[i][M + 1] = -1;
}
for (unsigned j = 0; j <= M + 1; ++j)
{
A[0][j] = A[N + 1][j] = B[0][j] = B[N + 1][j] = -1;
}
}
void lee()
{
border();
std::queue<std::pair<unsigned, unsigned>> Q_Rom, Q_Jul;
Q_Rom.push(std::make_pair(Rom.lin, Rom.col));
Q_Jul.push(std::make_pair(Jul.lin, Jul.col));
A[Rom.lin][Rom.col] = B[Jul.lin][Jul.col] = 1;
while (!Q_Rom.empty())
{
std::pair<unsigned, unsigned> cur_pos_Rom = Q_Rom.front();
Q_Rom.pop();
for (unsigned i = 0; i < nr_dirs; ++i)
{
int new_line_Rom = cur_pos_Rom.first + dx[i];
int new_col_Rom = cur_pos_Rom.second + dy[i];
if (A[new_line_Rom][new_col_Rom] == 0)
{
A[new_line_Rom][new_col_Rom] = A[cur_pos_Rom.first][cur_pos_Rom.second] + 1;
Q_Rom.push(std::make_pair(new_line_Rom, new_col_Rom));
}
}
}
while (!Q_Jul.empty())
{
std::pair<int, int> cur_pos_Jul = Q_Jul.front();
Q_Jul.pop();
for (unsigned i = 0; i < nr_dirs; ++i)
{
int new_line_Jul = cur_pos_Jul.first + dx[i];
int new_col_Jul = cur_pos_Jul.second + dy[i];
if (B[new_line_Jul][new_col_Jul] == 0)
{
B[new_line_Jul][new_col_Jul] = B[cur_pos_Jul.first][cur_pos_Jul.second] + 1;
Q_Jul.push(std::make_pair(new_line_Jul, new_col_Jul));
}
}
}
}
int main()
{
std::ifstream fisierIN("rj.in");
fisierIN >> N >> M; fisierIN.get();
for (unsigned i = 1; i <= N; ++i)
{
for (unsigned j = 1; j <= M; ++j)
{
char cur_chr = fisierIN.get();
if (cur_chr == 'X')
{
A[i][j] = B[i][j] = -1;
}
else if (cur_chr == 'R')
{
Rom.lin = i, Rom.col = j;
}
else if (cur_chr == 'J')
{
Jul.lin = i, Jul.col = j;
}
}
fisierIN.get();
}
fisierIN.close();
bool s = false;
lee();
std::ofstream fisierOUT("rj.out");
for (unsigned i = 1; i <= N; ++i)
{
for (unsigned j = 1; j <= M; ++j)
{
if (A[i][j] > 0 && A[i][j] == B[i][j])
{
fisierOUT << A[i][j] << " " << i << " " << j;
s = true;
break;
}
}
if (s)
{
break;
}
}
fisierOUT.close();
return 0;
}