(id:asi1024による)JOI本選予想問題：問題２ 迷子(A Stray Child)

問題文

http://d.hatena.ne.jp/asi1024/20101225/1293242247

解法

幼女から母親までの距離 >= 幼女から一番近いハンターまでの距離 のとき

幼女に一番近いハンターが先に幼女へ辿りつけるので無理

幼女から母親までの距離 < 幼女から一番近いハンターまでの距離 のとき

母親が幼女への最短経路を行ければ一番よい。

またこのとき、ハンターは母親が幼女への最短経路を行くのを妨げることができない。なぜなら、経路を妨げるには母親よりも先回りして経路に乗っておく必要があるが、もしそれが出来たとすると条件に矛盾するため。

よって

幅優先探索するだけでよい。

ソース

#include<cstdio>
#include<queue>
#include<utility>

using namespace std;

int H, W, N, dx[]={1,-1,0,0}, dy[]={0,0,1,-1};
char F[1024][1024];

typedef pair<pair<int, int>, int> st;

int bfs(int sx, int sy)
{
  int S = H*W, Y = H*W;
  queue<st> q;
  q.push(st(make_pair(sx, sy), 0));
  F[sy][sx] = 'X';
  while(!q.empty()) {
    int x = q.front().first.first, y = q.front().first.second;
    int s = q.front().second; q.pop();
    for(int i=0; i<4; ++i) {
      int nx = x+dx[i], ny = y+dy[i];
      if(F[ny][nx]==0 || F[ny][nx]=='X') continue;
      if(F[ny][nx]=='S') S=s+1;
      if(F[ny][nx]=='Y' || F[ny][nx]=='H') Y=min(Y, s+1);
      F[ny][nx] = 'X';
      q.push(st(make_pair(nx, ny), s+1));
    }
  }
  return S<Y ? S : -1;
}

int main()
{
  scanf("%d%d%d", &H, &W, &N);
  for(int i=1; i<=H; ++i)
    scanf("%s", &F[i][1]);
  for(int i=1; i<=H; ++i)
    for(int j=1; j<=W; ++j)
      if(F[i][j]=='G') {
	printf("%d\n", bfs(j, i));
	return 0;
      }
  return 0;
}