UVa12202

UVa12202
最大30×30のグリッド上に障害物とワープホールがある。
障害物の無い上下左右に隣接したセルに移動できる。
ワープホールに侵入すると、時間T (-10000 <= T <= 10000)を消費して別の場所に飛ばされる。
スタート地点からゴール地点まで到達可能であれば、(負の値になろうとも)最短時間を出力する。
到達できない場合は、どう到達できないのかを判定してゴニョゴニョ。

ベルマンフォードみたいに、値の更新を充分繰り返して試す。

#include <iostream>
#include <algorithm>

using namespace std;

const int H = 30 + 1;
const int W = 30 + 1;
const int inf = 1 << 29;

bool taboo[H][W];
pair<int, int> hole[H][W];
int t[H][W];
const int di[] = {-1, 1, 0, 0};
const int dj[] = {0, 0, -1, 1};

int solve(int h, int w)
{
  static int dist[H][W];
  static int cnt[H][W];
  fill(&dist[0][0], &dist[H-1][W], inf);
  fill(&cnt[0][0], &cnt[H-1][W], 0);
  dist[0][0] = 0;

  while (true) {
    bool flg = true;
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        if (dist[i][j] == inf) continue;
        if (taboo[i][j]) continue;
        if (i == h-1 && j == w-1) continue;
        if (6 * h * w < cnt[i][j]) return -inf;
        if (hole[i][j] == make_pair(-1, -1)) {
          const int di[] = {-1, 1, 0, 0};
          const int dj[] = {0, 0, -1, 1};
          for (int d = 0; d < 4; ++d) {
            int ni = i + di[d];
            int nj = j + dj[d];            
            if (ni < 0 || nj < 0) continue;
            if (h <= ni || w <= nj) continue;
            if (taboo[ni][nj]) continue;
            if (dist[ni][nj] > dist[i][j] + 1) {
              flg = false;
              dist[ni][nj] = dist[i][j] + 1;
              ++cnt[ni][nj];
            }
          }
        } else {
          int ni = hole[i][j].first;
          int nj = hole[i][j].second;
          if (dist[ni][nj] > dist[i][j] + t[i][j]) {
            flg = false;
            dist[ni][nj] = dist[i][j] + t[i][j];
            ++cnt[ni][nj];
          }
        }
      }
    }
    if (flg) break;
  }

  return dist[h-1][w-1];
}

int main(void)
{  
  int w, h;
  while (cin >> w >> h && (w | h)) {
    fill(&taboo[0][0], &taboo[H-1][W], false);
    fill(&hole[0][0], &hole[H-1][W], make_pair(-1, -1));

    int g, e;
    cin >> g;
    while (g--) {
      int i, j;
      cin >> j >> i;
      taboo[i][j] = true;
    }

    cin >> e;
    while (e--) {
      int si, sj, di, dj;
      cin >> sj >> si >> dj >> di;
      cin >> t[si][sj];
      hole[si][sj] = make_pair(di, dj);
    }

    int result = solve(h, w);
    if (result == -inf) cout << "Never" << endl;
    else if (inf <= result) cout << "Impossible" << endl;    
    else cout << result << endl;
  }
  return 0;
}