Pagini recente » Cod sursa (job #312098) | Cod sursa (job #1385763) | Cod sursa (job #2076009) | Cod sursa (job #2403364) | Cod sursa (job #2242318)
#include <fstream>
#include <queue>
using namespace std;
queue < pair <short, short> > q;
char c[105][105];
short rom[105][105], jul[105][105];
short n, m;
short dx[8] = {1, 1, 1, -1, -1, -1, 0, 0};
short dy[8] = {-1, 0, 1, -1, 0, 1, -1, 1};
const short oo = 20000;
void Read ()
{
ifstream fin ("rj.in");
fin >> n >> m;
fin.get();
for (int i = 1; i <= n; i++)
fin.getline(c[i] + 1, 101);
}
void Initiate ()
{
int i, j;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
rom[i][j] = jul[i][j] = oo;
}
void Board ()
{
short i, j;
for (i = 0; i <= n + 1; i++)
c[i][0] = c[i][m + 1] = 'X';
for (j = 0; j <= m + 1; j++)
c[0][j] = c[n + 1][j] = 'X';
}
void LeeR ()
{
while (!q.empty())
q.pop();
short i, j, k, x, y;
bool OK = true;
for (i = 1; i <= n && OK; i++)
for (j = 1; j <= m && OK; j++)
if (c[i][j] == 'R')
{
q.push({i, j});
rom[i][j] = 1;
OK = false;
}
while (!q.empty())
{
i = q.front().first;
j = q.front().second;
q.pop();
for (k = 0; k <= 7; k++)
{
x = i + dx[k];
y = j + dy[k];
if (c[x][y] == ' ' && rom[x][y] > 1 + rom[i][j])
{
rom[x][y] = 1 + rom[i][j];
q.push({x, y});
}
}
}
}
void LeeJ ()
{
while (!q.empty())
q.pop();
short i, j, k, x, y;
bool OK = true;
for (i = 1; i <= n && OK; i++)
for (j = 1; j <= m && OK; j++)
if (c[i][j] == 'J')
{
q.push({i, j});
jul[i][j] = 1;
OK = false;
}
while (!q.empty())
{
i = q.front().first;
j = q.front().second;
q.pop();
for (k = 0; k <= 7; k++)
{
x = i + dx[k];
y = j + dy[k];
if (c[x][y] == ' ' && jul[x][y] > 1 + jul[i][j])
{
jul[x][y] = 1 + jul[i][j];
q.push({x, y});
}
}
}
}
void Solve ()
{
ofstream fout ("rj.out");
short xf, yf, dmin, i, j;
dmin = oo;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
if (rom[i][j] == jul[i][j] && rom[i][j] != oo)
if (rom[i][j] < dmin)
{
dmin = rom[i][j];
xf = i;
yf = j;
}
}
fout << dmin << " " << xf << " " << yf << "\n";
fout.close();
}
void Afisare()
{
ofstream fout ("rj.out");
int i, j;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
fout << rom[i][j] << " ";
fout << "\n";
}
fout << "\n";
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
fout << jul[i][j] << " ";
fout << "\n";
}
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
fout << c[i][j];
fout << "\n";
}
}
int main()
{
Read();
Initiate();
Board();
LeeR();
LeeJ();
///Afisare();
Solve();
return 0;
}