问题描述
p220原题链接：UVaOJ 220 - Othello
相关说明：本题为《算法竞赛入门经典（第2版）》习题 4-3
解法一：模拟
大模拟，主要是判断能否落子 can_move_to 以及执行落子逻辑的 do_move 两个函数的逻辑要写对。对于尝试落子的点，需要看看其周围八个位置是否有邻居和自己颜色不同，如果有，就沿着这个方向去寻找下一个和自己颜色一致的棋子，如果能找到的话，说明这个地方可以落子。执行落子的时候，无非是对于当前能够落子的点位，需要将满足情况的每个方向上的棋子颜色进行变更（不要以为只有一个方向可以翻转哦）。
输出黑白棋子数量时，需要将宽度设为 2.
|
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; } |
|
1 |
#TODO |
