题目链接

小红的夹吃棋

题目描述

在一个3*3的棋盘上，小红和小紫正在玩"夹吃棋"。所谓"夹吃棋"，即如果存在一个白子，它的两侧（横向或者纵向）相邻都是黑子，则这个棋子将被"夹吃"；对于黑棋亦然。如果一个棋盘的局面没有一方被夹吃，或者黑白双方都被对面夹吃，则认为是平局。如果只有一方夹吃了另一方，则认为夹吃方赢，被夹吃方输。

小红执黑棋，小紫执白棋，现在给定一个局面，请你判断当前棋局是谁获胜。

输入:

  • 第一行输入一个正整数，代表询问的次数
  • 接下来每组询问输入三行，每行是一个长度为3的字符串，字符串仅由'o'、'*'、'.'组成
  • 其中'o'代表白棋，'*'代表黑棋，'.'代表未放置棋子

输出:

  • 对于每个棋局，输出一行字符串表示答案
  • 小红获胜输出"kou"，小紫获胜输出"yukari"，平局输出"draw"

解题思路

这是一个模拟问题，可以通过以下步骤解决：

  1. 关键发现：

    • 需要检查每个棋子是否被夹吃
    • 只需要检查横向和纵向
    • 需要分别统计黑白双方被夹吃的情况

  2. 模拟策略：

    • 遍历棋盘上的每个位置
    • 对每个棋子检查横向和纵向是否被夹吃
    • 根据双方被夹吃情况判断胜负

  3. 具体步骤：

    • 读入棋盘状态
    • 检查每个白子是否被黑子夹吃
    • 检查每个黑子是否被白子夹吃
    • 根据规则判断胜负

代码

#include <bits/stdc++.h>
using namespace std;

// 检查位置(i,j)的棋子是否被夹吃
bool isEaten(vector<string>& board, int i, int j, char target, char enemy) {
    // 检查横向
    if(j > 0 && j < 2 && board[i][j] == target && 
       board[i][j-1] == enemy && board[i][j+1] == enemy) {
        return true;
    }
    // 检查纵向
    if(i > 0 && i < 2 && board[i][j] == target && 
       board[i-1][j] == enemy && board[i+1][j] == enemy) {
        return true;
    }
    return false;
}

string solve(vector<string>& board) {
    bool white_eaten = false;  // 白子是否被夹吃
    bool black_eaten = false;  // 黑子是否被夹吃
    
    // 检查每个位置
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            if(board[i][j] == 'o' && isEaten(board, i, j, 'o', '*')) {
                white_eaten = true;
            }
            if(board[i][j] == '*' && isEaten(board, i, j, '*', 'o')) {
                black_eaten = true;
            }
        }
    }
    
    // 判断胜负
    if(white_eaten && !black_eaten) return "kou";      // 小红赢
    if(!white_eaten && black_eaten) return "yukari";   // 小紫赢
    return "draw";                                     // 平局
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while(T--) {
        vector<string> board(3);
        for(int i = 0; i < 3; i++) {
            cin >> board[i];
        }
        cout << solve(board) << '\n';
    }
    return 0;
}

import java.util.*;

public class Main {
    // 检查位置(i,j)的棋子是否被夹吃
    static boolean isEaten(char[][] board, int i, int j, char target, char enemy) {
        // 检查横向
        if(j > 0 && j < 2 && board[i][j] == target && 
           board[i][j-1] == enemy && board[i][j+1] == enemy) {
            return true;
        }
        // 检查纵向
        if(i > 0 && i < 2 && board[i][j] == target && 
           board[i-1][j] == enemy && board[i+1][j] == enemy) {
            return true;
        }
        return false;
    }
    
    static String solve(char[][] board) {
        boolean whiteEaten = false;  // 白子是否被夹吃
        boolean blackEaten = false;  // 黑子是否被夹吃
        
        // 检查每个位置
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                if(board[i][j] == 'o' && isEaten(board, i, j, 'o', '*')) {
                    whiteEaten = true;
                }
                if(board[i][j] == '*' && isEaten(board, i, j, '*', 'o')) {
                    blackEaten = true;
                }
            }
        }
        
        // 判断胜负
        if(whiteEaten && !blackEaten) return "kou";      // 小红赢
        if(!whiteEaten && blackEaten) return "yukari";   // 小紫赢
        return "draw";                                   // 平局
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0) {
            char[][] board = new char[3][3];
            for(int i = 0; i < 3; i++) {
                board[i] = sc.next().toCharArray();
            }
            System.out.println(solve(board));
        }
    }
}

def is_eaten(board, i, j, target, enemy):
    # 检查横向
    if j > 0 and j < 2 and board[i][j] == target and \
       board[i][j-1] == enemy and board[i][j+1] == enemy:
        return True
    # 检查纵向
    if i > 0 and i < 2 and board[i][j] == target and \
       board[i-1][j] == enemy and board[i+1][j] == enemy:
        return True
    return False

def solve(board):
    white_eaten = False  # 白子是否被夹吃
    black_eaten = False  # 黑子是否被夹吃
    
    # 检查每个位置
    for i in range(3):
        for j in range(3):
            if board[i][j] == 'o' and is_eaten(board, i, j, 'o', '*'):
                white_eaten = True
            if board[i][j] == '*' and is_eaten(board, i, j, '*', 'o'):
                black_eaten = True
    
    # 判断胜负
    if white_eaten and not black_eaten:
        return "kou"       # 小红赢
    if not white_eaten and black_eaten:
        return "yukari"    # 小紫赢
    return "draw"          # 平局

T = int(input())
for _ in range(T):
    board = [input() for _ in range(3)]
    print(solve(board))

算法及复杂度

  • 算法：模拟
  • 时间复杂度： - 每个棋局只需要常数时间检查
  • 空间复杂度： - 只需要常数空间存储棋盘