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

UVaOJ 220 - Othello

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

问题描述

p220

原题链接:UVaOJ 220 - Othello

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

解法一:模拟

大模拟,主要是判断能否落子 can_move_to 以及执行落子逻辑的 do_move 两个函数的逻辑要写对。对于尝试落子的点,需要看看其周围八个位置是否有邻居和自己颜色不同,如果有,就沿着这个方向去寻找下一个和自己颜色一致的棋子,如果能找到的话,说明这个地方可以落子。执行落子的时候,无非是对于当前能够落子的点位,需要将满足情况的每个方向上的棋子颜色进行变更(不要以为只有一个方向可以翻转哦)。

输出黑白棋子数量时,需要将宽度设为 2.

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
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
 
using namespace std;
 
char board[10][10], player;
int num_white, num_black;
vector<int> dir = {-1, 0, 1};
vector<pair<int, int>> buf;
 
bool legal(int r, int c) { return r >= 1 && r <= 8 && c >= 1 && c <= 8; }
 
bool can_move_to(int r, int c, char player) {
  if (board[r][c] != '-') return false;
  char opposite = (player == 'W' ? 'B' : 'W');
  for (auto dr : dir)
    for (auto dc : dir)
      if ((dr || dc) && legal(r + dr, c + dc) &&
          board[r + dr][c + dc] == opposite) {
        for (int pr = r + dr, pc = c + dc; legal(pr, pc); pr += dr, pc += dc) {
          if (board[pr][pc] == player) return true;
          if (board[pr][pc] == '-') break;
        }
      }
  return false;
}
 
void list_moves(char player) {
  int cnt = 0;
  for (int r = 1; r <= 8; ++r)
    for (int c = 1; c <= 8; ++c)
      if (can_move_to(r, c, player))
        cout << (cnt++ ? " (" : "(") << r << "," << c << ")";
  cout << (cnt ? "" : "No legal move.") << endl;
}
 
void do_move(int r, int c) {
  if (!can_move_to(r, c, player)) player = (player == 'W' ? 'B' : 'W');
  board[r][c] = player;
  player == 'W' ? num_white++ : num_black++;
  char opposite = (player == 'W' ? 'B' : 'W');
  for (auto dr : dir)
    for (auto dc : dir)
      if ((dr || dc) && legal(r + dr, c + dc) &&
          board[r + dr][c + dc] == opposite) {
        buf.clear();
        for (int pr = r + dr, pc = c + dc; legal(pr, pc); pr += dr, pc += dc) {
          if (board[pr][pc] == opposite) buf.push_back(pair<int, int>{pr, pc});
          if (board[pr][pc] == player) {
            for (auto p : buf) board[p.first][p.second] = player;
            num_white += player == 'W' ? buf.size() : -buf.size();
            num_black += player == 'B' ? buf.size() : -buf.size();
            break;
          }
          if (board[pr][pc] == '-') break;
        }
      }
  cout << "Black - " << setw(2) << num_black << " White - " << setw(2)
       << num_white << endl;
  player = opposite;
}
 
int main() {
  int num_game;
  cin >> num_game;
 
  for (int i = 0; i < num_game; ++i) {
    if (i) cout << endl;
    num_white = 0, num_black = 0;
    for (int r = 1; r <= 8; ++r)
      for (int c = 1; c <= 8; ++c) {
        cin >> board[r][c];
        board[r][c] == 'W' ? num_white++ : num_black++;
      }
    cin >> player;
 
    string command;
    while (cin >> command && command != "Q") {
      if (command == "L") list_moves(player);
      if (command[0] == 'M') do_move(command[1] - '0', command[2] - '0');
    }
    for (int r = 1; r <= 8; ++r)
      for (int c = 1; c <= 8; ++c) cout << board[r][c] << (c == 8 ? "\n" : "");
  }
  return 0;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz