Pagini recente » Cod sursa (job #1470999) | Cod sursa (job #277959) | Cod sursa (job #3213407) | Cod sursa (job #809303) | Cod sursa (job #258188)
Cod sursa(job #258188)
#include <cstdio>
#include <queue>
#include <algorithm>
#define FIN "rj.in"
#define FOUT "rj.out"
#define N 177
using namespace std;
const int dx[]={0,1,0,-1};
const int dy[]={-1,0,1,0};
queue < pair <int,int> > q;
pair <int,int> cr,cj,r[N][N];
int n,m,tmin = N * N,mi,mj;
void read()
{
int i,j;
char c;
freopen(FIN,"r",stdin);
scanf("%d%d\n", &n, &m);
mi = n; mj = m;
for (i = 1; i <= n; ++i)
{
for ( j = 1; j <= m; ++j)
{
scanf("%c", &c);
if (c == ' ')
r[i][j].first = r[i][j].second = -1;
if (c == 'X')
r[i][j].first = r[i][j].second = -2;
if (c == 'J')
{
cj = make_pair(i,j);
r[i][j].second = 0;
r[i][j].first = -1;
}
if (c == 'R')
{
cr = make_pair(i,j);
r[i][j].first = 0;
r[i][j].second = -1;
}
}
scanf("\n");
}
}
void write()
{
freopen(FOUT,"w",stdout);
printf("%d %d %d\n", tmin, mi, mj);
/*for (i = 1; i <= n; ++i)
{
for (j = 1; j <= n; ++j)
printf("(%d,%d) ",r[i][j].first,r[i][j].second);
printf("\n");
}*/
}
int solve()
{
int i;
pair <int,int> p1,p2;
for (i = 1; i <= n; ++i)
{
r[i][0].first = r[i][0].second = -2;
r[0][i].first = r[0][i].second = -2;
}
q.push(cr);
while ( q.empty() == false )
{
p1 = q.front();
q.pop();
for (i = 0; i <= 3; ++i)
//for (j = 0; j <=3; ++j)
if ( p1.first + dx[i] <= n && p1.second + dy[i] <= m )
{
p2 = make_pair( p1.first + dx[i], p1.second + dy[i]);
if (r[p2.first][p2.second].first == -1)
{
r[p2.first][p2.second].first = r[p1.first][p1.second].first + 1;
q.push(p2);
}
}
}
q.push(cj);
while ( q.empty() == false )
{
p1 = q.front();
q.pop();
for (i = 0; i <= 3; ++i)
if ( p1.first + dx[i] <= n && p1.second + dy[i] <= m )
{
p2 = make_pair( p1.first + dx[i], p1.second + dy[i]);
if ( r[p2.first][p2.second].second == -1)
{
r[p2.first][p2.second].second = r[p1.first][p1.second].second + 1;
if ( r[p2.first][p2.second].first == r[p2.first][p2.second].second)
{
if (r[p2.first][p2.second].first <= tmin)
{
mi = p2.first; mj = p2.second;
tmin = r[p2.first][p2.second].first;
}
else if (r[p2.first][p2.second].first == tmin && (p2.first <= mi || (p2.first == mi && p2.second == mj)))
tmin = r[p2.first][p2.second].first;
}
q.push(p2);
}
}
}
return -1;
}
int main()
{
read();
solve();
write();
}