[THUPC2019]鸭棋

直接暴力模拟啥事没有。

题意

请看原题面：https://loj.ac/p/6619

source: THUPC 2019

思路

维护两个数组，分别是王的直走步数组和士的斜走步数组。

每次走完一步后（以及走第一步前）暴力计算每一个子可以走到哪些位置，然后一切就好办了，就是复杂度有点高，是 $\Theta(n^2m^2Q)$ 的，不过能过。

王

直接遍历王数组，检验是否能走。

士

遍历士数组，检验是否能走。

兵

遍历王数组和士数组。

马

遍历两层，第一步的王数组与第二步的士数组。检验 $\Delta x$ 和 $\Delta y$ 是否皆非 0。如果第一步走王步会到达一个棋子就不枚举第二步。

鸭

与马类似，枚举两层，第一步的王数组和二、三步的士数组。同样检验走第二步之后的 $\Delta x $ 和 $\Delta y$ 是否皆非 0。如果第一步走王步会到达一个棋子就不枚举第二步，如果第二步会到达一个棋子就抛弃这个选择。

象

遍历士数组，如果走一步没有阻挡就检验走两步是否可行。

车

遍历士数组，枚举走了多少步，一直走直到遇到一个棋子，如果遇到对方棋子就停下并认为可以吃到那个子。

细节

这里用 std::unordered_set 来存储可走的地方。

这里用 std::array 来存储棋盘，在枚举可达位置的时候使用 std::array::at() 来访问信息，并在外围套上一个 try {} catch(...) {} ，以避免麻烦的边界判断。

这里用正负来区分红、蓝方。

不知道为什么第 8 行和第 9 行的初始状态写反了……调了半个小时……

代码

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <array>

namespace mirai {

enum piece {
  K = 1, // king
  G, // guard
  B, // bishop
  N, // knight
  R, // rook
  D, // duck
  P // pawn
};

constexpr char name[8][20] = {"", "captain", "guard", "elephant", "horse", "car", "duck", "soldier"};

template <typename type>
class custom_hash {
 public:
  type operator()(const type& x) const {
    return x;
  }
};
template <>
class custom_hash<int> {
 public:
  std::size_t operator()(const int& x) const {
    return x ^ 0x19260817;
  }
};
template <>
class custom_hash<std::pair<int, int>> {
 public:
  std::size_t operator()(const std::pair<int, int>& x) const {
    return x.first ^ x.second;
  }
};

std::array<std::array<int, 9>, 10> board = {{
  {{R, N, B, G, K, G, B, N, R}},
  {{}},
  {{D, 0, 0, 0, 0, 0, 0, 0, D}},
  {{P, 0, P, 0, P, 0, P, 0, P}},
  {{}},
  {{}},
  {{-P,  0, -P,  0, -P,  0, -P,  0, -P}},
  {{-D,  0,  0,  0,  0,  0,  0,  0, -D}},
  {{}},
  {{-R, -N, -B, -G, -K, -G, -B, -N, -R}}
}};
std::unordered_set<std::pair<int, int>, custom_hash<std::pair<int, int>>> go[10][9];

constexpr int kdx[4] = {0, 0, 1, -1};
constexpr int kdy[4] = {1, -1, 0, 0};
constexpr int gdx[4] = {-1, 1, 1, -1};
constexpr int gdy[4] = {1, -1, 1, -1};

void check() {
  for (int x = 0; x < 10; ++x) {
    for (int y = 0; y < 9; ++y) {
      go[x][y].clear();
      if (board[x][y] == 0) { continue; }
      auto &piece = board[x][y];
      int army = piece < 0 ? -1 : 1;
      int type = piece / army;
      switch (type) {
       case K: {
         for (int i = 0; i < 4; ++i) {
           try {
             if (board.at(x + kdx[i]).at(y + kdy[i]) * army <= 0) {
               go[x][y].insert({x + kdx[i], y + kdy[i]});
             }
           } catch (...) {}
         }
         break;
       }
       case G: {
         for (int i = 0; i < 4; ++i) {
           try {
             if (board.at(x + gdx[i]).at(y + gdy[i]) * army <= 0) {
               go[x][y].insert({x + gdx[i], y + gdy[i]});
             }
           } catch (...) {}
         }
         break;
       }
       case B: {
         for (int i = 0; i < 4; ++i) {
           try {
             if (board.at(x + gdx[i]).at(y + gdy[i]) == 0 && 
                 board.at(x + gdx[i] * 2).at(y + gdy[i] * 2) * army <= 0) {
               go[x][y].insert({x + gdx[i] * 2, y + gdy[i] * 2});
             }
           } catch (...) {}
         }
         break;
       }
       case N: {
         for (int i = 0; i < 4; ++i) {
           for (int j = 0; j < 4; ++j) {
             int dx = kdx[i] + gdx[j], dy = kdy[i] + gdy[j];
             try {
               if (board.at(x + kdx[i]).at(y + kdy[i]) == 0 && dx && dy &&
                   board.at(x + dx).at(y + dy) * army <= 0) {
                 go[x][y].insert({x + dx, y + dy});
               }
             } catch (...) {}
           }
         }
         break;
       }
       case R: {
         for (int i = 0; i < 4; ++i) {
           try {
             for (int k = 1; k <= 9; ++k) {
               auto &&tmp = board.at(x + k * kdx[i]).at(y + k * kdy[i]);
               if (tmp * army <= 0) {
                 go[x][y].insert({x + k * kdx[i], y + k * kdy[i]});
               }
               if (tmp * army == 0) { continue; }
               break;
             }
           } catch (...) {}
         }
         break;
       }
       case D: {
         for (int i = 0; i < 4; ++i) {
           for (int j = 0; j < 4; ++j) {
             int dx = kdx[i] + gdx[j], dy = kdy[i] + gdy[j];
             try {
               if (board.at(x + kdx[i]).at(y + kdy[i]) == 0 && dx && dy && board.at(x + dx).at(y + dy) == 0 &&
                   board.at(x + dx + gdx[j]).at(y + dy + gdy[j]) * army <= 0) {
                 go[x][y].insert({x + dx + gdx[j], y + dy + gdy[j]});
               }
             } catch (...) {} 
           }
         }
         break;
       }
       case P: {
         for (int i = 0; i < 4; ++i) {
           try {
             if (board.at(x + kdx[i]).at(y + kdy[i]) * army <= 0) {
               go[x][y].insert({x + kdx[i], y + kdy[i]});
             }
           } catch (...) {}
         }
         for (int i = 0; i < 4; ++i) {
           try {
             if (board.at(x + gdx[i]).at(y + gdy[i]) * army <= 0) {
               go[x][y].insert({x + gdx[i], y + gdy[i]});
             }
           } catch (...) {}
         }
         break;
       }
      }
    }
  }
}

int main(int argc, char** argv) {
  int q;
  std::scanf("%d", &q);
  int army = 1;
  bool unchecked = true, game_ended = false;
  for (int test = 0; test < q; ++test) {
    int xs, ys, xt, yt;
    std::scanf("%d%d%d%d", &xs, &ys, &xt, &yt);
    // if (1 || test == 22) {
      // for (int i = 0; i < 10; ++i) {
        // for (int j = 0; j < 9; ++j) {
          // std::printf("%2d ", board[i][j]);
        // }
        // std::printf("\n");
      // }
      // std::printf("%d %d %d %d\n", xs, ys, xt, yt);
    // }
    if (unchecked) { check(); }
    if (go[xs][ys].find({xt, yt}) == go[xs][ys].end() || game_ended || board[xs][ys] * army <= 0) {
      std::puts("Invalid command");
      continue;
    }
    std::printf("%s %s;", board[xs][ys] > 0 ? "red" : "blue", name[std::abs(board[xs][ys])]);
    if (board[xt][yt] == 0) {
      std::printf("NA;");
    } else {
      std::printf("%s %s;", board[xt][yt] > 0 ? "red" : "blue", name[std::abs(board[xt][yt])]);
    }
    board[xt][yt] = board[xs][ys];
    board[xs][ys] = 0;
    check();
    // if (1 || test == 22) {
      // for (auto i : go[9][8]) {
        // std::printf("(%d, %d)\n", i.first, i.second);
      // }
    // }
    // for (auto i : go[6][6]) {
      // std::printf("(%d, %d)\n", i.first, i.second);
    // }
    int rkx = -1, rky = -1, bkx = -1, bky = -1; // Blue King, Red King
    for (int i = 0; i < 10; ++i) {
      for (int j = 0; j < 9; ++j) {
        if (board[i][j] == K) {
          rkx = i;
          rky = j;
        }
        if (board[i][j] == -K) {
          bkx = i;
          bky = j;
        }
      }
    }
    army = -army;
    if (rkx == -1 || bkx == -1) {
      std::printf("no;yes\n");
      game_ended = true;
      continue;
    }
    bool checking = false;
    for (int i = 0; i < 10 && !checking; ++i) {
      for (int j = 0; j < 9; ++j) {
        if (go[i][j].find({rkx, rky}) != go[i][j].end() || 
            go[i][j].find({bkx, bky}) != go[i][j].end()) {
          checking = true;
          break;
        }
      }
    }
    std::printf("%s;no\n", checking ? "yes" : "no");
  }
  return 0;
}

} // namespace mirai

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}