POJ 1024: Tester Program

poj.org

問題概要

縦 マス、横 マスの二次元グリッドがある。グリッドの左から 列目、下から 行目のマスをマス と呼ぶ。

マス から始めて隣接したマスに移動することを何度か繰り返した。移動の経路が文字列 として与えられる。 の 文字目が U, D, L, R であるとき、 回目でそれぞれ上、下、左、右に隣接するマスに移動したことを示す。グリッドの外に移動しようとしたり、同じマスを二度以上訪れるような経路は与えられないことが保証されている。

グリッドの隣接する 2 つのマスの組の間に壁を 個配置し、迷路を作った。 番目の壁はマス と の間に配置されている。迷路の始点はマス であり、終点は移動を終えたマスである。文字列 で示された経路がこの迷路の唯一の最短路であり、この条件を満たすために余分な壁がない (つまり、壁を 1 つ取り除くと文字列 で示された経路は必ずこの迷路の唯一の最短路ではなくなる) なら CORRECT、そうでないなら INCORRECT と出力せよ。

制約

• 以外の入力はすべて整数
• 
• は U, D, L, R のみからなる
• 文字列 で示された経路ではグリッドの外に移動することはない
• 文字列 で示された経路では同じマスを二度以上訪れることはない
• 
• 
• マス は辺を共有する
• (たぶん)
• (たぶん)

解法

まず、文字列 で示された経路に従って移動して終点を求め、経路上に壁がないか調べます。(実は、テストケースが弱いので経路上に壁があるかどうかの判定は行わなくても AC になります。)

迷路の最短路とその個数を BFS で計算することで、文字列 で示された経路が迷路の唯一の最短路であるか判定することができます。個数は大きくなりすぎないように、 との min を取っておきます。

余分な壁がないことの判定でそれぞれの壁について BFS を行うと、計算量が となり は最大で になりうるので TLE してしまうので、適切に前計算を行い高速に判定することを考えます。

ある壁が条件を満たすために必要である条件は、その壁を取り除いたときその場所を通る最短路が元の迷路の最短路 (上の判定をすべて通過したという仮定のもとで、これは に等しい) 以下であることです。

よって、始点からマス への最短路を , 終点からマス への最短路を とおくと、壁 を取り除いたときその場所を から に向かう方向に通る最短路は , から に向かう方向に通る最短路は なので、壁 が必要であることは であること同値になります。

それぞれの壁について必要性を で計算できたので、これでこの問題が解けました。

実装

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <utility>
using namespace std;
vector<int> dy, dx;
const int INF = 1000000;
int main(){
  dy = vector<int>(4);
  dy[0] = -1;
  dy[1] = 1;
  dy[2] = 0;
  dy[3] = 0;
  dx = vector<int>(4);
  dx[0] = 0;
  dx[1] = 0;
  dx[2] = -1;
  dx[3] = 1;
  int t;
  cin >> t;
  for (int i = 0; i < t; i++){
    int W, H;
    cin >> W >> H;
    string S;
    cin >> S;
    int M;
    cin >> M;
    vector<int> x1(M), y1(M), x2(M), y2(M);
    for (int j = 0; j < M; j++){
      cin >> x1[j] >> y1[j] >> x2[j] >> y2[j];
      if (x1[j] > x2[j]){
        swap(x1[j], x2[j]);
      }
      if (y1[j] > y2[j]){
        swap(y1[j], y2[j]);
      }
    }
    vector<vector<vector<bool>>> E(H, vector<vector<bool>>(W, vector<bool>(4, true)));
    for (int j = 0; j < W; j++){
      E[0][j][0] = false;
      E[H - 1][j][1] = false;
    }
    for (int j = 0; j < H; j++){
      E[j][0][2] = false;
      E[j][W - 1][3] = false;
    }
    for (int j = 0; j < M; j++){
      if (x1[j] == x2[j]){
        E[y1[j]][x1[j]][1] = false;
        E[y2[j]][x1[j]][0] = false;
      }
      if (y1[j] == y2[j]){
        E[y1[j]][x1[j]][3] = false;
        E[y1[j]][x2[j]][2] = false;
      }
    }
    int N = S.size();
    bool ok = true;
    int cy = 0, cx = 0;
    for (int j = 0; j < N; j++){
      int ny = cy, nx = cx;
      if (S[j] == 'U'){
        ny++;
        if (!E[cy][cx][1]){
          ok = false;
        }
      }
      if (S[j] == 'D'){
        ny--;
        if (!E[cy][cx][0]){
          ok = false;
        }
      }
      if (S[j] == 'L'){
        nx--;
        if (!E[cy][cx][2]){
          ok = false;
        }
      }
      if (S[j] == 'R'){
        nx++;
        if (!E[cy][cx][3]){
          ok = false;
        }
      }
      cy = ny;
      cx = nx;
    }
    if (!ok){
      cout << "INCORRECT" << endl;
    } else {
      vector<vector<int>> d1(H, vector<int>(W, INF));
      vector<vector<int>> cnt(H, vector<int>(W, 0));
      d1[0][0] = 0;
      cnt[0][0] = 1;
      queue<pair<int, int>> Q1;
      Q1.push(make_pair(0, 0));
      while (!Q1.empty()){
        int y = Q1.front().first;
        int x = Q1.front().second;
        Q1.pop();
        for (int j = 0; j < 4; j++){
          if (E[y][x][j]){
            int y2 = y + dy[j];
            int x2 = x + dx[j];
            if (d1[y2][x2] == INF){
              d1[y2][x2] = d1[y][x] + 1;
              cnt[y2][x2] = cnt[y][x];
              Q1.push(make_pair(y2, x2));
            } else if (d1[y2][x2] == d1[y][x] + 1){
              cnt[y2][x2] = min(cnt[y2][x2] + cnt[y][x], 2);
            }
          }
        }
      }
      if (cnt[cy][cx] >= 2){
        cout << "INCORRECT" << endl;
      } else if (d1[cy][cx] != N){
        cout << "INCORRECT" << endl;
      } else {
        vector<vector<int>> d2(H, vector<int>(W, INF));
        d2[cy][cx] = 0;
        queue<pair<int, int>> Q2;
        Q2.push(make_pair(cy, cx));
        while (!Q2.empty()){
          int y = Q2.front().first;
          int x = Q2.front().second;
          Q2.pop();
          for (int j = 0; j < 4; j++){
            if (E[y][x][j]){
              int y2 = y + dy[j];
              int x2 = x + dx[j];
              if (d2[y2][x2] == INF){
                d2[y2][x2] = d2[y][x] + 1;
                Q2.push(make_pair(y2, x2));
              }
            }
          }
        }
        for (int j = 0; j < M; j++){
          if (d1[y1[j]][x1[j]] + d2[y2[j]][x2[j]] + 1 > N && d1[y2[j]][x2[j]] + d2[y1[j]][x1[j]] + 1 > N){
            ok = false;
          }
        }
        if (!ok){
          cout << "INCORRECT" << endl;
        } else {
          cout << "CORRECT" << endl;
        }
      }
    }
  }
}