1. 项目背景与问题定义黑白棋又称翻转棋是一种经典的策略性棋盘游戏在华为OD机试中常作为考察编程能力的题目出现。这类题目通常要求考生在N×N的棋盘上模拟棋子移动规则并计算特定条件下的合法移动范围。这个问题的核心在于理解黑白棋的基本规则棋盘由8×8或N×N的方格组成双方轮流落子每次落子必须能够翻转对手的棋子合法移动必须至少翻转对手的一枚棋子游戏结束时以棋盘上棋子数量多少判定胜负在编程实现层面我们需要解决以下几个关键点棋盘状态的表示与存储合法移动位置的判断算法棋子翻转的逻辑实现移动范围的计算与输出2. 核心算法设计与实现2.1 棋盘表示方法在代码实现中我们通常使用二维数组来表示棋盘状态。以Python为例# 初始化N×N棋盘 def init_board(size8): board [[None for _ in range(size)] for _ in range(size)] mid size // 2 board[mid-1][mid-1] W board[mid][mid] W board[mid-1][mid] B board[mid][mid-1] B return board这种表示方法的优势在于直观对应棋盘物理结构便于通过坐标直接访问特定位置方便进行边界检查2.2 合法移动判断算法判断一个位置是否为合法落子点是本问题的核心。算法需要检查8个方向上、下、左、右、四个对角线是否存在可翻转的对手棋子def is_valid_move(board, x, y, player): if board[x][y] is not None: return False opponent B if player W else W directions [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] for dx, dy in directions: tx, ty x dx, y dy if 0 tx len(board) and 0 ty len(board) and board[tx][ty] opponent: tx dx ty dy while 0 tx len(board) and 0 ty len(board): if board[tx][ty] is None: break if board[tx][ty] player: return True tx dx ty dy return False2.3 棋子翻转逻辑实现当确认一个位置是合法落子点后需要实际执行棋子翻转操作def make_move(board, x, y, player): if not is_valid_move(board, x, y, player): return False board[x][y] player opponent B if player W else W directions [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] for dx, dy in directions: tx, ty x dx, y dy to_flip [] while 0 tx len(board) and 0 ty len(board) and board[tx][ty] opponent: to_flip.append((tx, ty)) tx dx ty dy if 0 tx len(board) and 0 ty len(board) and board[tx][ty] player: for fx, fy in to_flip: board[fx][fy] player break return True3. 移动范围计算与输出3.1 计算所有合法移动位置为了满足题目要求我们需要计算当前玩家所有可能的合法移动位置def get_valid_moves(board, player): valid_moves [] for i in range(len(board)): for j in range(len(board)): if is_valid_move(board, i, j, player): valid_moves.append((i, j)) return valid_moves3.2 输出移动范围根据华为OD机试的常见要求输出格式通常需要特定处理def print_valid_moves(board, player): valid_moves get_valid_moves(board, player) if not valid_moves: print(No legal moves.) return # 创建标记棋盘 marker_board [[0 for _ in range(len(board))] for _ in range(len(board))] for x, y in valid_moves: marker_board[x][y] 1 # 按要求格式输出 for row in marker_board: print( .join(map(str, row)))4. 完整解决方案实现4.1 Python实现class Reversi: def __init__(self, size8): self.size size self.board self.init_board(size) def init_board(self, size): board [[None for _ in range(size)] for _ in range(size)] mid size // 2 board[mid-1][mid-1] W board[mid][mid] W board[mid-1][mid] B board[mid][mid-1] B return board def is_valid_move(self, x, y, player): if self.board[x][y] is not None: return False opponent B if player W else W directions [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] for dx, dy in directions: tx, ty x dx, y dy if 0 tx self.size and 0 ty self.size and self.board[tx][ty] opponent: tx dx ty dy while 0 tx self.size and 0 ty self.size: if self.board[tx][ty] is None: break if self.board[tx][ty] player: return True tx dx ty dy return False def get_valid_moves(self, player): valid_moves [] for i in range(self.size): for j in range(self.size): if self.is_valid_move(i, j, player): valid_moves.append((i, j)) return valid_moves def print_valid_moves(self, player): valid_moves self.get_valid_moves(player) if not valid_moves: print(No legal moves.) return marker_board [[0 for _ in range(self.size)] for _ in range(self.size)] for x, y in valid_moves: marker_board[x][y] 1 for row in marker_board: print( .join(map(str, row))) # 使用示例 if __name__ __main__: game Reversi(8) game.print_valid_moves(B)4.2 JavaScript实现class Reversi { constructor(size 8) { this.size size; this.board this.initBoard(size); } initBoard(size) { const board Array(size).fill().map(() Array(size).fill(null)); const mid Math.floor(size / 2); board[mid-1][mid-1] W; board[mid][mid] W; board[mid-1][mid] B; board[mid][mid-1] B; return board; } isValidMove(x, y, player) { if (this.board[x][y] ! null) { return false; } const opponent player B ? W : B; const directions [ [-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1] ]; for (const [dx, dy] of directions) { let tx x dx; let ty y dy; if (tx 0 tx this.size ty 0 ty this.size this.board[tx][ty] opponent) { tx dx; ty dy; while (tx 0 tx this.size ty 0 ty this.size) { if (this.board[tx][ty] null) { break; } if (this.board[tx][ty] player) { return true; } tx dx; ty dy; } } } return false; } getValidMoves(player) { const validMoves []; for (let i 0; i this.size; i) { for (let j 0; j this.size; j) { if (this.isValidMove(i, j, player)) { validMoves.push([i, j]); } } } return validMoves; } printValidMoves(player) { const validMoves this.getValidMoves(player); if (validMoves.length 0) { console.log(No legal moves.); return; } const markerBoard Array(this.size).fill().map(() Array(this.size).fill(0)); for (const [x, y] of validMoves) { markerBoard[x][y] 1; } for (const row of markerBoard) { console.log(row.join( )); } } } // 使用示例 const game new Reversi(8); game.printValidMoves(B);5. 算法优化与性能考虑5.1 时间复杂度分析基础实现的时间复杂度判断单个位置是否合法O(N)最坏情况下需要检查8个方向每个方向最多N步获取所有合法移动O(N³)N²个位置每个位置O(N)检查5.2 优化思路方向检查提前终止一旦在某个方向找到合法条件即可终止该方向的检查缓存合法移动在游戏状态未改变时缓存计算结果位运算优化对于固定大小的棋盘如8×8可以使用位运算加速5.3 优化后的合法移动判断def is_valid_move_optimized(board, x, y, player): if board[x][y] is not None: return False opponent B if player W else W size len(board) directions [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] for dx, dy in directions: tx, ty x dx, y dy found_opponent False while 0 tx size and 0 ty size: if board[tx][ty] is None: break if board[tx][ty] player: if found_opponent: return True break if board[tx][ty] opponent: found_opponent True tx dx ty dy return False6. 测试用例设计与验证6.1 单元测试设计良好的测试用例应覆盖以下场景初始棋盘的合法移动边缘位置的移动无合法移动的情况多个方向可翻转的情况非法移动尝试6.2 Python测试示例import unittest class TestReversi(unittest.TestCase): def setUp(self): self.game Reversi(8) def test_initial_valid_moves_black(self): valid_moves self.game.get_valid_moves(B) expected [(2,3), (3,2), (4,5), (5,4)] self.assertEqual(set(valid_moves), set(expected)) def test_invalid_move(self): self.assertFalse(self.game.is_valid_move(0, 0, B)) def test_no_valid_moves(self): # 创建一个无合法移动的场景 custom_board [[None]*8 for _ in range(8)] custom_board[3][3] B self.game.board custom_board self.assertEqual(self.game.get_valid_moves(W), []) if __name__ __main__: unittest.main()6.3 边界情况处理棋盘边界确保算法正确处理棋盘边缘位置最小棋盘处理2×2等小棋盘的极端情况全满棋盘当棋盘被完全填满时的处理交替玩家确保交替落子时逻辑正确7. 华为OD机试注意事项7.1 输入输出格式华为OD机试通常有严格的输入输出要求需要注意输入可能是字符串形式需要正确解析输出格式必须完全匹配题目要求注意处理行尾空格等细节问题7.2 性能限制机试题目通常有执行时间和内存限制Python避免使用深层递归JavaScript注意V8引擎的优化限制对于大N情况如N100需要优化算法7.3 常见错误棋盘索引越界未正确处理初始棋局方向检查遗漏某些情况输出格式不符合要求未处理无合法移动的特殊情况8. 扩展与变种问题8.1 变种问题示例限制移动方向只允许水平或垂直移动不同棋盘大小处理非对称棋盘多玩家版本三人或四人黑白棋移动代价不同位置落子有不同的代价8.2 高级算法方向Minimax算法实现AI对战蒙特卡洛树搜索优化AI决策Zobrist哈希快速判断棋盘状态重复并行计算使用多线程加速搜索在实际开发中黑白棋算法可以进一步优化为更高效的实现特别是在需要处理大型棋盘或实现AI对战的情况下。对于华为OD机试而言掌握基础实现并确保正确性是最关键的要求。 华为OD机试：黑白棋合法移动算法实现与优化
1. 项目背景与问题定义黑白棋又称翻转棋是一种经典的策略性棋盘游戏在华为OD机试中常作为考察编程能力的题目出现。这类题目通常要求考生在N×N的棋盘上模拟棋子移动规则并计算特定条件下的合法移动范围。这个问题的核心在于理解黑白棋的基本规则棋盘由8×8或N×N的方格组成双方轮流落子每次落子必须能够翻转对手的棋子合法移动必须至少翻转对手的一枚棋子游戏结束时以棋盘上棋子数量多少判定胜负在编程实现层面我们需要解决以下几个关键点棋盘状态的表示与存储合法移动位置的判断算法棋子翻转的逻辑实现移动范围的计算与输出2. 核心算法设计与实现2.1 棋盘表示方法在代码实现中我们通常使用二维数组来表示棋盘状态。以Python为例# 初始化N×N棋盘 def init_board(size8): board [[None for _ in range(size)] for _ in range(size)] mid size // 2 board[mid-1][mid-1] W board[mid][mid] W board[mid-1][mid] B board[mid][mid-1] B return board这种表示方法的优势在于直观对应棋盘物理结构便于通过坐标直接访问特定位置方便进行边界检查2.2 合法移动判断算法判断一个位置是否为合法落子点是本问题的核心。算法需要检查8个方向上、下、左、右、四个对角线是否存在可翻转的对手棋子def is_valid_move(board, x, y, player): if board[x][y] is not None: return False opponent B if player W else W directions [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] for dx, dy in directions: tx, ty x dx, y dy if 0 tx len(board) and 0 ty len(board) and board[tx][ty] opponent: tx dx ty dy while 0 tx len(board) and 0 ty len(board): if board[tx][ty] is None: break if board[tx][ty] player: return True tx dx ty dy return False2.3 棋子翻转逻辑实现当确认一个位置是合法落子点后需要实际执行棋子翻转操作def make_move(board, x, y, player): if not is_valid_move(board, x, y, player): return False board[x][y] player opponent B if player W else W directions [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] for dx, dy in directions: tx, ty x dx, y dy to_flip [] while 0 tx len(board) and 0 ty len(board) and board[tx][ty] opponent: to_flip.append((tx, ty)) tx dx ty dy if 0 tx len(board) and 0 ty len(board) and board[tx][ty] player: for fx, fy in to_flip: board[fx][fy] player break return True3. 移动范围计算与输出3.1 计算所有合法移动位置为了满足题目要求我们需要计算当前玩家所有可能的合法移动位置def get_valid_moves(board, player): valid_moves [] for i in range(len(board)): for j in range(len(board)): if is_valid_move(board, i, j, player): valid_moves.append((i, j)) return valid_moves3.2 输出移动范围根据华为OD机试的常见要求输出格式通常需要特定处理def print_valid_moves(board, player): valid_moves get_valid_moves(board, player) if not valid_moves: print(No legal moves.) return # 创建标记棋盘 marker_board [[0 for _ in range(len(board))] for _ in range(len(board))] for x, y in valid_moves: marker_board[x][y] 1 # 按要求格式输出 for row in marker_board: print( .join(map(str, row)))4. 完整解决方案实现4.1 Python实现class Reversi: def __init__(self, size8): self.size size self.board self.init_board(size) def init_board(self, size): board [[None for _ in range(size)] for _ in range(size)] mid size // 2 board[mid-1][mid-1] W board[mid][mid] W board[mid-1][mid] B board[mid][mid-1] B return board def is_valid_move(self, x, y, player): if self.board[x][y] is not None: return False opponent B if player W else W directions [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] for dx, dy in directions: tx, ty x dx, y dy if 0 tx self.size and 0 ty self.size and self.board[tx][ty] opponent: tx dx ty dy while 0 tx self.size and 0 ty self.size: if self.board[tx][ty] is None: break if self.board[tx][ty] player: return True tx dx ty dy return False def get_valid_moves(self, player): valid_moves [] for i in range(self.size): for j in range(self.size): if self.is_valid_move(i, j, player): valid_moves.append((i, j)) return valid_moves def print_valid_moves(self, player): valid_moves self.get_valid_moves(player) if not valid_moves: print(No legal moves.) return marker_board [[0 for _ in range(self.size)] for _ in range(self.size)] for x, y in valid_moves: marker_board[x][y] 1 for row in marker_board: print( .join(map(str, row))) # 使用示例 if __name__ __main__: game Reversi(8) game.print_valid_moves(B)4.2 JavaScript实现class Reversi { constructor(size 8) { this.size size; this.board this.initBoard(size); } initBoard(size) { const board Array(size).fill().map(() Array(size).fill(null)); const mid Math.floor(size / 2); board[mid-1][mid-1] W; board[mid][mid] W; board[mid-1][mid] B; board[mid][mid-1] B; return board; } isValidMove(x, y, player) { if (this.board[x][y] ! null) { return false; } const opponent player B ? W : B; const directions [ [-1,-1], [-1,0], [-1,1], [0,-1], [0,1], [1,-1], [1,0], [1,1] ]; for (const [dx, dy] of directions) { let tx x dx; let ty y dy; if (tx 0 tx this.size ty 0 ty this.size this.board[tx][ty] opponent) { tx dx; ty dy; while (tx 0 tx this.size ty 0 ty this.size) { if (this.board[tx][ty] null) { break; } if (this.board[tx][ty] player) { return true; } tx dx; ty dy; } } } return false; } getValidMoves(player) { const validMoves []; for (let i 0; i this.size; i) { for (let j 0; j this.size; j) { if (this.isValidMove(i, j, player)) { validMoves.push([i, j]); } } } return validMoves; } printValidMoves(player) { const validMoves this.getValidMoves(player); if (validMoves.length 0) { console.log(No legal moves.); return; } const markerBoard Array(this.size).fill().map(() Array(this.size).fill(0)); for (const [x, y] of validMoves) { markerBoard[x][y] 1; } for (const row of markerBoard) { console.log(row.join( )); } } } // 使用示例 const game new Reversi(8); game.printValidMoves(B);5. 算法优化与性能考虑5.1 时间复杂度分析基础实现的时间复杂度判断单个位置是否合法O(N)最坏情况下需要检查8个方向每个方向最多N步获取所有合法移动O(N³)N²个位置每个位置O(N)检查5.2 优化思路方向检查提前终止一旦在某个方向找到合法条件即可终止该方向的检查缓存合法移动在游戏状态未改变时缓存计算结果位运算优化对于固定大小的棋盘如8×8可以使用位运算加速5.3 优化后的合法移动判断def is_valid_move_optimized(board, x, y, player): if board[x][y] is not None: return False opponent B if player W else W size len(board) directions [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] for dx, dy in directions: tx, ty x dx, y dy found_opponent False while 0 tx size and 0 ty size: if board[tx][ty] is None: break if board[tx][ty] player: if found_opponent: return True break if board[tx][ty] opponent: found_opponent True tx dx ty dy return False6. 测试用例设计与验证6.1 单元测试设计良好的测试用例应覆盖以下场景初始棋盘的合法移动边缘位置的移动无合法移动的情况多个方向可翻转的情况非法移动尝试6.2 Python测试示例import unittest class TestReversi(unittest.TestCase): def setUp(self): self.game Reversi(8) def test_initial_valid_moves_black(self): valid_moves self.game.get_valid_moves(B) expected [(2,3), (3,2), (4,5), (5,4)] self.assertEqual(set(valid_moves), set(expected)) def test_invalid_move(self): self.assertFalse(self.game.is_valid_move(0, 0, B)) def test_no_valid_moves(self): # 创建一个无合法移动的场景 custom_board [[None]*8 for _ in range(8)] custom_board[3][3] B self.game.board custom_board self.assertEqual(self.game.get_valid_moves(W), []) if __name__ __main__: unittest.main()6.3 边界情况处理棋盘边界确保算法正确处理棋盘边缘位置最小棋盘处理2×2等小棋盘的极端情况全满棋盘当棋盘被完全填满时的处理交替玩家确保交替落子时逻辑正确7. 华为OD机试注意事项7.1 输入输出格式华为OD机试通常有严格的输入输出要求需要注意输入可能是字符串形式需要正确解析输出格式必须完全匹配题目要求注意处理行尾空格等细节问题7.2 性能限制机试题目通常有执行时间和内存限制Python避免使用深层递归JavaScript注意V8引擎的优化限制对于大N情况如N100需要优化算法7.3 常见错误棋盘索引越界未正确处理初始棋局方向检查遗漏某些情况输出格式不符合要求未处理无合法移动的特殊情况8. 扩展与变种问题8.1 变种问题示例限制移动方向只允许水平或垂直移动不同棋盘大小处理非对称棋盘多玩家版本三人或四人黑白棋移动代价不同位置落子有不同的代价8.2 高级算法方向Minimax算法实现AI对战蒙特卡洛树搜索优化AI决策Zobrist哈希快速判断棋盘状态重复并行计算使用多线程加速搜索在实际开发中黑白棋算法可以进一步优化为更高效的实现特别是在需要处理大型棋盘或实现AI对战的情况下。对于华为OD机试而言掌握基础实现并确保正确性是最关键的要求。