MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 1589 - Xiangqi
AOAPC II

UVaOJ 1589 - Xiangqi

Chai
2021-11-24 0:00:00在线评测阅读 314

问题描述

p1589

原题链接:UVaOJ 1589 - Xiangqi

相关说明:本题为《算法竞赛入门经典(第2版)》习题 4-1

解法一:模拟

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

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

  • 如果黑将当前移动能够直接飞过去把对面红帅吃了,输出 NO;
  • 否则尝试所有可以移动的方向,看是否存在某种移动后不会被红方吃掉,有任意解则输出 NO;
  • 上述条件都不存在的话,输出 YES.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#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;
}
Python
1
#TODO
AOAPC II UVaOJ 字符串
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz