UVaOJ 1589 - Xiangqi

问题描述

解法一：模拟

大模拟，需要注意蛮多细节。我的实现中用 board 把当前棋盘落字有无的情况存下来， board[x][y]=0 表示对应位置没有红方棋子，同时将红方棋子按照类型进行记录。这里设置了一个辅助函数 interval 表示两个棋子之间有多少个间隔棋子，可以用来判断能否直接飞将帅、车能否吃以及炮能否打过去；而在判断马棋盘上的马能否吃到移动后的黑将时，用到了一个规律，即如果能吃到，两个棋子之间的斜线距离是根号 5, 且 board[mx][my] 处没有棋子阻挡。代码中用到了比较多的 dir定义的技巧来判断移动的方向，可以少写些 if-else.

判断黑方是否已经走投无路的整体思路是：

如果黑将当前移动能够直接飞过去把对面红帅吃了，输出 NO;
否则尝试所有可以移动的方向，看是否存在某种移动后不会被红方吃掉，有任意解则输出 NO;
上述条件都不存在的话，输出 YES.

#include <bits/stdc++.h>

using namespace std;

int board[11][10];  // Value 0 means no red piece here
int black_gx, black_gy, white_gx, white_gy;
vector<pair<int, int>> chariot, horse, cannon;

int interval(int x1, int y1, int x2, int y2) {
  int num = 0;
  if (x1 != x2 && y1 != y2) return -1;  // not in the same line
  if (x1 == x2 && y1 == y2) return -1;  // in the same point
  if (x1 == x2) {
    int dir = (y2 - y1) > 0 ? 1 : -1;
    for (int p = y1 + dir; p != y2; p += dir)
      if (board[x1][p]) ++num;
  } else if (y1 == y2) {
    int dir = (x2 - x1) > 0 ? 1 : -1;
    for (int p = x1 + dir; p != x2; p += dir)
      if (board[p][y1]) ++num;
  }
  return num;
}

bool capture(int x, int y) {
  if (interval(x, y, white_gx, white_gy) == 0) return true;
  for (auto r : chariot)
    if (interval(x, y, r.first, r.second) == 0) return true;
  for (auto h : horse)
    if (abs(pow(x - h.first, 2) + pow(y - h.second, 2) - 5) < 1e-5) {
      int mx = h.first + (x - h.first) / 2;
      int my = h.second + (y - h.second) / 2;
      if (!board[mx][my]) return true;
    }
  for (auto c : cannon)
    if (interval(x, y, c.first, c.second) == 1) return true;
  return false;
}

int main() {
  int n, px, py;
  string type, blank_line;
  while (cin >> n >> black_gx >> black_gy) {
    if (!n && !black_gx && !black_gy) break;

    memset(board, 0, sizeof(board));
    chariot.clear(), horse.clear(), cannon.clear();

    while (n--) {
      cin >> type >> px >> py;
      board[px][py] = 1;
      if (type == "G") white_gx = px, white_gy = py;
      if (type == "R") chariot.push_back(pair<int, int>{px, py});
      if (type == "H") horse.push_back(pair<int, int>{px, py});
      if (type == "C") cannon.push_back(pair<int, int>{px, py});
    }

    // Flying general
    if (interval(black_gx, black_gy, white_gx, white_gy) == 0) {
      cout << "NO" << endl;
      continue;
    }

    if (interval(black_gx, black_gy, white_gx, white_gy) == 0 ||
        (black_gx > 1 && !capture(black_gx - 1, black_gy)) ||
        (black_gx < 3 && !capture(black_gx + 1, black_gy)) ||
        (black_gy > 4 && !capture(black_gx, black_gy - 1)) ||
        (black_gy < 6 && !capture(black_gx, black_gy + 1)))
      cout << "NO" << endl;
    else
      cout << "YES" << endl;

    getline(cin, blank_line);
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int board[11][10]; // Value 0 means no red piece here

int black_gx, black_gy, white_gx, white_gy;

vector<pair<int, int>> chariot, horse, cannon;

int interval(int x1, int y1, int x2, int y2) {

int num = 0;

if (x1 != x2 && y1 != y2) return -1; // not in the same line

if (x1 == x2 && y1 == y2) return -1; // in the same point

if (x1 == x2) {

int dir = (y2 - y1) > 0 ? 1 : -1;

for (int p = y1 + dir; p != y2; p += dir)

if (board[x1][p]) ++num;

} else if (y1 == y2) {

int dir = (x2 - x1) > 0 ? 1 : -1;

for (int p = x1 + dir; p != x2; p += dir)

if (board[p][y1]) ++num;

}

return num;

}

bool capture(int x, int y) {

if (interval(x, y, white_gx, white_gy) == 0) return true;

for (auto r : chariot)

if (interval(x, y, r.first, r.second) == 0) return true;

for (auto h : horse)

if (abs(pow(x - h.first, 2) + pow(y - h.second, 2) - 5) < 1e-5) {

int mx = h.first + (x - h.first) / 2;

int my = h.second + (y - h.second) / 2;

if (!board[mx][my]) return true;

}

for (auto c : cannon)

if (interval(x, y, c.first, c.second) == 1) return true;

return false;

}

int main() {

int n, px, py;

string type, blank_line;

while (cin >> n >> black_gx >> black_gy) {

if (!n && !black_gx && !black_gy) break;

memset(board, 0, sizeof(board));

chariot.clear(), horse.clear(), cannon.clear();

while (n--) {

cin >> type >> px >> py;

board[px][py] = 1;

if (type == "G") white_gx = px, white_gy = py;

if (type == "R") chariot.push_back(pair<int, int>{px, py});

if (type == "H") horse.push_back(pair<int, int>{px, py});

if (type == "C") cannon.push_back(pair<int, int>{px, py});

}

// Flying general

if (interval(black_gx, black_gy, white_gx, white_gy) == 0) {

cout << "NO" << endl;

continue;

}

if (interval(black_gx, black_gy, white_gx, white_gy) == 0 ||

(black_gx > 1 && !capture(black_gx - 1, black_gy)) ||

(black_gx < 3 && !capture(black_gx + 1, black_gy)) ||

(black_gy > 4 && !capture(black_gx, black_gy - 1)) ||

(black_gy < 6 && !capture(black_gx, black_gy + 1)))

cout << "NO" << endl;

else

cout << "YES" << endl;

getline(cin, blank_line);

}

return 0;

}

#TODO

#TODO

AOAPC II UVaOJ 字符串