Pagini recente » Cod sursa (job #1775431) | Arhiva de probleme | Cod sursa (job #1119136) | Cod sursa (job #1336154) | Cod sursa (job #1592541)
#include <fstream>
#include <climits>
#define MAX 100
using namespace std;
ifstream fin ("rj.in");
ofstream fout ("rj.out");
void read ();
void bordare ();
void Romeo ();
void Julieta ();
void solve ();
void print ();
unsigned short int N, M;
char s[MAX];
const short int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const short int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1};
short int a[MAX][MAX], mat[MAX][MAX];
unsigned short int i, j, k, xr, yr, xj, yj;
int pr, ul, x, y, lin, col, tmin=INT_MAX;
int main ()
{
read ();
solve ();
print ();
return 0;
}
struct coord
{
int x, y;
};
coord q[MAX];
void read ()
{
fin >> N >> M;
fin.get();
for (i=1; i<=N; i++)
{
fin.getline(s,MAX);
for (j=0; j<M; j++)
if (s[j] == ' ')
a[i][j+1] = 0;
else if (s[j] == 'X')
a[i][j+1] = 1;
else if (s[j] == 'R')
{
xr = i;
yr = j+1;
}
else
{
xj = i;
yj = j+1;
}
}
fin.close();
for (i=1; i<=N; i++)
for (j=1; j<=M; j++)
mat[i][j] = a[i][j];
}
void solve ()
{
bordare ();
Romeo ();
Julieta ();
}
void print ()
{
for (i=1; i<=N; i++)
for (j=1; j<=M; j++)
if (a[i][j] == mat[i][j] && a[i][j]>1 && a[i][j]-1 < tmin)
{
tmin = a[i][j] - 1;
lin = i;
col = j;
}
fout << tmin << " " << lin << " " << col;
}
void bordare ()
{
for (i=0; i<=N+1; i++)
mat[i][0] = mat[i][M] = a[i][0] = a[i][M] = -1;
for (i=0; i<=M+1; i++)
mat[0][i] = mat[N][i] = a[0][i] = a[N][i] = -1;
}
void Romeo ()
{
pr = ul = 0;
a[xr][yr] = 2;
q[ul].x = xr;
q[ul].y = yr;
while (pr <= ul)
{
i = q[pr].x;
j = q[pr].y;
pr++;
for (k=0; k<8; k++)
{
x = i + dx[k];
y = j + dy[k];
if (a[x][y] == 0)
{
ul++;
q[ul].x = x;
q[ul].y = y;
a[x][y] = a[i][j] + 1;
}
}
}
}
void Julieta ()
{
pr = ul = 0;
mat[xj][yj] = 2;
q[ul].x = xj;
q[ul].y = yj;
while (pr <= ul)
{
i = q[pr].x;
j = q[pr].y;
pr++;
for (k=0; k<4; k++)
{
x = i + dx[k];
y = j + dy[k];
if (mat[x][y] == 0)
{
ul++;
q[ul].x = x;
q[ul].y = y;
mat[x][y] = mat[i][j] + 1;
}
}
}
}