読者です 読者をやめる 読者になる 読者になる

AOJ0156 Moats around the Castle

解法
拡張ダイクストラ。各エッジをわたるコストが0または1で、1のみではないことを考えると幅優先ではなくコストの小さいものをキューから取り出す拡張ダイクストラがいいと思うけど、多分幅優先でも出来る。

問題では場外から目的地に向かうが、スタート地点が増えてしまうので、逆に目的地から場外に外れるまでの最小コストを求める形にすると良い。障壁が連続している場合は一回のみコストに換算することに気をつける。マップ読み込み時に目的地の '&' のいちを記録すると同時に '.' に変換してしまうと安全。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
int H, W;
char grid[110][110];
 
int const dx[4] = {-1,1,0,0};
int const dy[4] = {0,0,-1,1};
 
int memo[101][101];
 
inline bool IN(int x, int y) {
  return 0<=x && x<W && 0<=y && y<H;
}
 
int const INF = 1<<29;
 
int main() {
   
  while(cin >> W >> H && W) {
     
    int sx, sy;
     
    for(int i=0; i<H; i++) {
      for(int j=0; j<W; j++) {
        cin >> grid[i][j];
        if(grid[i][j] == '&') {
          sx = j, sy = i;
          grid[i][j] = '.';
        }
      }
    }
     
    int ans = 1<<29;
     
    memset(memo, -1, sizeof(memo));
    typedef pair<int, int> Pii;
    typedef pair<int, Pii> Piii;
     
    priority_queue<Piii> Q;
    Q.push(Piii(0, Pii(sx, sy)));
    while(!Q.empty()) {
      Piii piii = Q.top(); Q.pop();
      int const x = piii.second.first;
      int const y = piii.second.second;
      int const cost = -piii.first;
       
      if(x == 0 || y == 0 || x == W-1 || y == H-1) {
        cout << cost << endl;
        break;
      }
       
      for(int k=0; k<4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if(IN(nx, ny)) {
          int ncost = cost + (grid[y][x] == '.' && grid[ny][nx] == '#');
          if(memo[ny][nx] == -1 || memo[ny][nx] > ncost) {
            memo[ny][nx] = ncost;
            Q.push(Piii(-ncost, Pii(nx, ny)));
          }
        }
      }
    }
     
  }
   
  return 0;
}