Pagini recente » Cod sursa (job #3162980) | Cod sursa (job #1537107) | Cod sursa (job #1779365) | Cod sursa (job #2345167) | Cod sursa (job #258669)
Cod sursa(job #258669)
#include <cstdio>
#include <queue>
#include <algorithm>
#define FIN "rj.in"
#define FOUT "rj.out"
#define N 110
using namespace std;
const int dx[]={0,1,1,1,0,-1,-1,-1};
const int dy[]={-1,-1,0,1,1,1,0,-1};
queue < pair <int,int> > q;
pair <int,int> cr,cj,r[N][N];
int n,m,tmin = N * N,mi,mj;
void proba()
{
int i,j;
for (i = 1; i <= n; ++i)
{
for (j = 1; j <= m; ++j)
printf("(%d,%d)\t",r[i][j].first,r[i][j].second);
printf("\n");
}
printf("\n");
}
void read()
{
int i,j;
char c[N];
freopen(FIN,"r",stdin);
scanf("%d%d\n", &n, &m);
mi = n; mj = m;
for (i = 1; i <= n; ++i)
{
fgets(c,N,stdin);
for ( j = 0; j < m; ++j)
{
if (c[j] == ' ')
r[i][j+1].first = r[i][j+1].second = -1;
if (c[j] == 'X')
r[i][j+1].first = r[i][j+1].second = -2;
if (c[j] == 'J')
{
cj = make_pair(i,j+1);
r[i][j+1].second = 1;
r[i][j+1].first = -1;
}
if (c[j] == 'R')
{
cr = make_pair(i,j+1);
r[i][j+1].first = 1;
r[i][j+1].second = -1;
}
}
}
}
void write()
{
freopen(FOUT,"w",stdout);
printf("%d %d %d\n", tmin, mi, mj);
}
int solve()
{
int i;
pair <int,int> p1,p2;
for (i = 1; i <= n; ++i)
r[i][0].first = r[i][0].second = -2;
for (i = 1; i <= m; ++i)
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 <= 7; ++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].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 <= 7; ++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();
}