Pagini recente » Istoria paginii runda/ant5/clasament | Cod sursa (job #1768895) | Cod sursa (job #2472821) | Cod sursa (job #2345536) | Cod sursa (job #1609051)
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
using namespace std;
int n, m;
int matR[105][105];
int matJ[105][105];
int dx[8] = {-1, 0, 1, -1, 1, 1, 0, -1};
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
struct Punct
{
int x;
int y;
Punct(int a = 0, int b = 0)
{
x = a;
y = b;
}
} startR, startJ;
queue<Punct> q;
void Debug()
{
for (int i=0; i<=n+1; i++)
{
for (int j=0; j<=m+1; j++)
{
cerr<<matR[i][j]<<" ";
}
cerr<<"\n";
}
}
void LeeRomeo()
{
q.push(Punct(startR.x, startR.y));
matR[startR.x][startR.y] = 1;
Punct aux;
while(!q.empty())
{
aux = q.front();
for (int i=0; i<8; i++)
{
if (matR[aux.x + dx[i]][aux.y + dy[i]] == 0)
{
matR[aux.x + dx[i]][aux.y + dy[i]] = matR[aux.x][aux.y] + 1;
q.push(Punct(aux.x + dx[i], aux.y + dy[i]));
}
}
q.pop();
}
}
void LeeJulieta()
{
q.push(Punct(startJ.x, startJ.y));
matJ[startJ.x][startJ.y] = 1;
Punct aux;
while(!q.empty())
{
aux = q.front();
for (int i=0; i<8; i++)
{
if (matJ[aux.x + dx[i]][aux.y + dy[i]] == 0)
{
matJ[aux.x + dx[i]][aux.y + dy[i]] = matJ[aux.x][aux.y] + 1;
if (matJ[aux.x + dx[i]][aux.y + dy[i]] == matR[aux.x + dx[i]][aux.y + dy[i]])
{
printf("%d %d %d", matJ[aux.x + dx[i]][aux.y + dy[i]], aux.x + dx[i], aux.y + dy[i]);
return;
}
q.push(Punct(aux.x + dx[i], aux.y + dy[i]));
}
}
q.pop();
}
}
void Solve()
{
LeeRomeo();
LeeJulieta();
}
void Bordare()
{
for (int i=0; i<=n+1; i++)
{
for (int j=0; j<=m+1; j++)
{
if (i==0 || i==n+1 || j==0 || j==m+1)
matR[i][j] = -1;
}
}
}
void Read()
{
char aux;
scanf("%d %d\n", &n, &m);
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
{
matR[i][j] = 0;
scanf("%c", &aux);
if (aux == 'R')
{
startR.x = i;
startR.y = j;
}
else if (aux == 'J')
{
startJ.x = i;
startJ.y = j;
}
else if (aux == 'X')
matR[i][j] = -1;
}
scanf("\n");
}
Bordare();
memcpy(matJ, matR, sizeof(matR));
}
int main()
{
freopen("rj.in", "r", stdin);
freopen("rj.out", "w", stdout);
Read();
Solve();
// Debug();
return 0;
}