题解 | #小红的夹吃棋#

题目链接

小红的夹吃棋

题目描述

在一个 $3 \times 3$ 棋盘上，小红（执黑 *）与小紫（执白 o）进行“夹吃棋”。规则：若某棋子在横向或纵向上被对方两个棋子夹住（即三连棋中，中间为己方棋子，两边为对方棋子），该中间棋子被“夹吃”。

胜负判定：

若仅一方存在被夹吃的棋子，则对方获胜。
若双方均无被夹吃的棋子，或双方均有被夹吃的棋子，则为平局。

给定若干局面，判断结果。

解题思路

本题的核心是根据规则，检查棋盘上是否存在小红的棋子被吃，以及是否存在小紫的棋子被吃。

我们可以使用两个布尔变量，例如 kou_eaten 和 yukari_eaten，来分别记录小红（黑方）和小紫（白方）是否被吃子。

具体的检查过程如下：

初始化：将 kou_eaten 和 yukari_eaten 都设为 false。
遍历检查：由于棋盘是固定的 $3 \times 3$ 大小，我们可以直接检查所有可能形成“夹吃”的直线。总共有6条线需要检查：3条横线和3条竖线。
- 检查横向：
  - 对于第 i 行（i 从0到2），检查 board[i] 是否为 "o*o"。如果是，说明小红的棋子被吃，将 kou_eaten 设为 true。
  - 检查 board[i] 是否为 "*o*"。如果是，说明小紫的棋子被吃，将 yukari_eaten 设为 true。
- 检查纵向：
  - 对于第 j 列（j 从0到2），检查 board[0][j], board[1][j], board[2][j] 组成的字符串是否为 "o*o"。如果是，将 kou_eaten 设为 true。
  - 检查是否为 "*o*"。如果是，将 yukari_eaten 设为 true。
判定结果：在检查完所有6条线后，根据 kou_eaten 和 yukari_eaten 的最终状态来判定胜负。
- 如果 kou_eaten 为 true 且 yukari_eaten 为 false，则小紫获胜（yukari）。
- 如果 kou_eaten 为 false 且 yukari_eaten 为 true，则小红获胜（kou）。
- 其他所有情况（两者都为 true 或都为 false），均为平局（draw）。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void solve() {
    vector<string> board(3);
    for (int i = 0; i < 3; ++i) {
        cin >> board[i];
    }

    bool kou_eaten = false;
    bool yukari_eaten = false;

    // 检查横向
    for (int i = 0; i < 3; ++i) {
        if (board[i] == "o*o") {
            kou_eaten = true;
        }
        if (board[i] == "*o*") {
            yukari_eaten = true;
        }
    }

    // 检查纵向
    for (int j = 0; j < 3; ++j) {
        string col;
        col += board[0][j];
        col += board[1][j];
        col += board[2][j];
        if (col == "o*o") {
            kou_eaten = true;
        }
        if (col == "*o*") {
            yukari_eaten = true;
        }
    }

    if (kou_eaten && !yukari_eaten) {
        cout << "yukari" << endl;
    } else if (!kou_eaten && yukari_eaten) {
        cout << "kou" << endl;
    } else {
        cout << "draw" << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        String[] board = new String[3];
        for (int i = 0; i < 3; i++) {
            board[i] = sc.next();
        }

        boolean kou_eaten = false;
        boolean yukari_eaten = false;

        // 检查横向
        for (int i = 0; i < 3; i++) {
            if (board[i].equals("o*o")) {
                kou_eaten = true;
            }
            if (board[i].equals("*o*")) {
                yukari_eaten = true;
            }
        }

        // 检查纵向
        for (int j = 0; j < 3; j++) {
            String col = "" + board[0].charAt(j) + board[1].charAt(j) + board[2].charAt(j);
            if (col.equals("o*o")) {
                kou_eaten = true;
            }
            if (col.equals("*o*")) {
                yukari_eaten = true;
            }
        }

        if (kou_eaten && !yukari_eaten) {
            System.out.println("yukari");
        } else if (!kou_eaten && yukari_eaten) {
            System.out.println("kou");
        } else {
            System.out.println("draw");
        }
    }
}

def solve():
    board = [input() for _ in range(3)]
    
    kou_eaten = False
    yukari_eaten = False

    # 检查横向
    for i in range(3):
        if board[i] == "o*o":
            kou_eaten = True
        if board[i] == "*o*":
            yukari_eaten = True

    # 检查纵向
    for j in range(3):
        col = board[0][j] + board[1][j] + board[2][j]
        if col == "o*o":
            kou_eaten = True
        if col == "*o*":
            yukari_eaten = True
            
    if kou_eaten and not yukari_eaten:
        print("yukari")
    elif not kou_eaten and yukari_eaten:
        print("kou")
    else:
        print("draw")

t = int(input())
for _ in range(t):
    solve()

算法及复杂度

算法：模拟 / 暴力枚举
时间复杂度：对于每个测试用例，我们都对一个 $3 \times 3$ 的棋盘进行常数次数的检查（3行和3列）。因此，每个测试用例的时间复杂度是 $\mathcal{O}(1)$ 。
空间复杂度：需要存储一个 $3 \times 3$ 的棋盘，是常数大小。因此，空间复杂度为 $\mathcal{O}(1)$ 。