题解 | #小红的夹吃棋#

题目链接

小红的夹吃棋

题目描述

在一个 3*3 的棋盘上，小红（黑棋 '*'）和小紫（白棋 'o'）玩“夹吃棋”。

规则如下：

如果一个白子 ('o') 的两侧（横向或纵向）相邻都是黑子 ('*')，则这个白子被“夹吃”。
如果一个黑子 ('*') 的两侧（横向或纵向）相邻都是白子 ('o')，则这个黑子被“夹吃”。

胜负判断：

小红获胜 (kou)：只有白棋被夹吃。
小紫获胜 (yukari)：只有黑棋被夹吃。
平局 (draw)：双方都被夹吃，或者双方都没有被夹吃。

给定一个局面，判断棋局结果。

解题思路

这是一个基于固定规则的棋盘状态判断问题。由于棋盘大小仅为 3*3，我们可以通过直接检查所有可能构成“夹吃”的模式来确定结果。

解题步骤如下：

设定状态标志：我们需要两个布尔类型的标志来记录战况：
- kou_pincers: 记录小红（黑棋）是否夹吃了小紫（白棋）。
- yukari_pincers: 记录小紫（白棋）是否夹吃了小红（黑棋）。初始时，将这两个标志都设为 false。
遍历检查：我们需要检查所有可能的三元组，看它们是否构成了夹吃。在 3*3 棋盘上，这样的三元组只有 6 个：3 个横向行和 3 个纵向列。
- 检查所有行：对于每一行，检查是否存在 *o* （小红夹吃）或 o*o （小紫夹吃）的模式。
- 检查所有列：对于每一列，检查是否存在 *o* 或 o*o 的模式。
- 一旦在任何行或列中找到 *o* 模式，就将 kou_pincers 设为 true。
- 一旦在任何行或列中找到 o*o 模式，就将 yukari_pincers 设为 true。
最终裁决：在检查完所有 6 个三元组后，根据两个标志位的最终状态来判断结果：
- 如果 kou_pincers 为 true 且 yukari_pincers 为 false，输出 "kou"。
- 如果 kou_pincers 为 false 且 yukari_pincers 为 true，输出 "yukari"。
- 其他所有情况（即 kou_pincers 和 yukari_pincers 同为 true 或同为 false），输出 "draw"。

这种方法通过简单的遍历和条件判断，直接模拟了题目的裁决过程，逻辑清晰且易于实现。

代码

c++
java
python

#include <bits/stdc++.h>

using namespace std;

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

    bool kou_pincers = false;
    bool yukari_pincers = false;

    // 检查行
    for (int i = 0; i < 3; ++i) {
        if (board[i][0] == '*' && board[i][1] == 'o' && board[i][2] == '*') {
            kou_pincers = true;
        }
        if (board[i][0] == 'o' && board[i][1] == '*' && board[i][2] == 'o') {
            yukari_pincers = true;
        }
    }

    // 检查列
    for (int j = 0; j < 3; ++j) {
        if (board[0][j] == '*' && board[1][j] == 'o' && board[2][j] == '*') {
            kou_pincers = true;
        }
        if (board[0][j] == 'o' && board[1][j] == '*' && board[2][j] == 'o') {
            yukari_pincers = true;
        }
    }

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

int main() {
    ios_base::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) {
        char[][] board = new char[3][3];
        for (int i = 0; i < 3; i++) {
            board[i] = sc.next().toCharArray();
        }

        boolean kouPincers = false;
        boolean yukariPincers = false;

        // 检查行
        for (int i = 0; i < 3; i++) {
            if (board[i][0] == '*' && board[i][1] == 'o' && board[i][2] == '*') {
                kouPincers = true;
            }
            if (board[i][0] == 'o' && board[i][1] == '*' && board[i][2] == 'o') {
                yukariPincers = true;
            }
        }

        // 检查列
        for (int j = 0; j < 3; j++) {
            if (board[0][j] == '*' && board[1][j] == 'o' && board[2][j] == '*') {
                kouPincers = true;
            }
            if (board[0][j] == 'o' && board[1][j] == '*' && board[2][j] == 'o') {
                yukariPincers = true;
            }
        }

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

import sys

def solve():
    board = [sys.stdin.readline().strip() for _ in range(3)]

    kou_pincers = False
    yukari_pincers = False

    # 检查行
    for i in range(3):
        if board[i] == "*o*":
            kou_pincers = True
        if board[i] == "o*o":
            yukari_pincers = True

    # 检查列
    for j in range(3):
        col = board[0][j] + board[1][j] + board[2][j]
        if col == "*o*":
            kou_pincers = True
        if col == "o*o":
            yukari_pincers = True

    if kou_pincers and not yukari_pincers:
        print("kou")
    elif not kou_pincers and yukari_pincers:
        print("yukari")
    else:
        print("draw")


def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：模拟 / 暴力枚举
时间复杂度：对于每个测试用例，我们执行固定次数的检查（3 行和 3 列）。因此，每个测试用例的时间复杂度是 $\mathcal{O}(1)$ 。对于 $T$ 个测试用例，总时间复杂度为 $\mathcal{O}(T)$ 。
空间复杂度：对于每个测试用例，我们只需要存储 3x3 的棋盘，所以空间复杂度是 $\mathcal{O}(1)$ 。