Pagini recente » Cod sursa (job #1770995) | Cod sursa (job #1247505) | Cod sursa (job #562042) | Cod sursa (job #1901134) | Cod sursa (job #877849)
Cod sursa(job #877849)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<vector>
using namespace std ;
#define maxn 105
#define maxcoada 10001
#define maxdir 8
char sir[maxn] ;
struct punct
{
int x, y ;
};
int dx[maxdir] = { 0, 1, 0, -1, -1, 1, -1, 1 } ;
int dy[maxdir] = { 1, 0, -1, 0, -1, 1, 1, -1 } ;
int n, m ;
char harta[maxn][maxn] ;
int xr, yr ;
int xj, yj ;
int romeo[maxn][maxn] ;
int julieta[maxn][maxn] ;
void lee(int xs, int ys, int dist[maxn][maxn] )
{
punct coada[maxcoada] ;
for(int i = 0; i <= n + 1; ++i )
for(int j = 0; j <= m + 1 ; ++j )
dist[i][j] = -1 ;
int len = 0 ;
coada[len].x = xs ;
coada[len].y = ys ;
dist[xs][ys] = 1 ;
for(int i = 0; i <= len; ++i )
{
int xn = coada[i].x ;
int yn = coada[i].y ;
for(int j = 0; j < maxdir; ++j )
{
int xact = xn + dx[j] ;
int yact = yn + dy[j] ;
if( harta[ xact ][ yact ] == ' ' && dist[ xact ][ yact ] == -1 )
{
dist[ xact ][ yact ] = dist[xn][yn] + 1 ;
++len ;
coada[len].x = xact ;
coada[len].y = yact ;
}
}
}
}
int main()
{
freopen("rj.in", "r", stdin);
freopen("rj.out", "w", stdout);
scanf("%d%d\n", &n, &m);
for(int i = 0; i <= n + 1; ++i )
harta[i][0] = harta[i][ m + 1 ] = 'X' ;
for(int i = 0; i <= m + 1; ++i )
harta[0][i] = harta[ n + 1 ][i] = 'X' ;
for(int i = 1; i <= n; ++i )
{
fgets( sir, maxn+5, stdin ) ;
// cout<<strlen(sir)<<" "<<sir<<endl ;
for(int j = 1; j <= m; ++j )
{
harta[i][j] = sir[j-1] ;
if( harta[i][j] == 'R' )
{
xr = i ;
yr = j ;
harta[i][j] = ' ' ;
}
if( harta[i][j] == 'J' )
{
xj = i ;
yj = j ;
harta[i][j] = ' ' ;
}
}
/*
char ch ;
for(int j = 1; j <= m; ++j )
{
scanf("%c", &ch);
harta[i][j] = ch ;
if( harta[i][j] == 'R' )
{
xr = i ;
yr = j ;
harta[i][j] = ' ' ;
}
if( harta[i][j] == 'J' )
{
xj = i ;
yj = j ;
harta[i][j] = ' ' ;
}
}
scanf("%c", &ch);
*/
}
lee( xr, yr, romeo ) ;
lee( xj, yj, julieta ) ;
int tmin = maxcoada ;
int xmin, ymin ;
for(int i = 1; i <= n; ++i )
{
for(int j = 1; j <= m; ++j )
{
if( romeo[i][j] == julieta[i][j] )
{
if( romeo[i][j] < tmin && romeo[i][j] != -1 )
{
tmin = romeo[i][j] ;
xmin = i ;
ymin = j ;
}
}
}
}
printf("%d %d %d\n", tmin, xmin, ymin);
return 0 ;
}