题解 | #小红的夹吃棋#

题目链接

BGN13 小红的夹吃棋

题目描述

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

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

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

输入描述

第一行输入整数 $t$ （询问次数）。每组询问输入3行，每行长度为3的字符串，仅含 o（白子）、*（黑子）、.（未落子），表示棋盘状态。

输出描述

对每局输出一行：

小红胜输出 kou
小紫胜输出 yukari
平局输出 draw

样例

输入

3
...
o*o
...
o**
ooo
..*
o*o
*o*
o*o

输出

yukari
kou
draw

解题思路

本题需要根据“夹吃”规则判断棋局的胜负。由于棋盘大小固定为 $3 \cdot 3$ ，我们可以直接暴力检查所有可能被“夹吃”的情况。

“夹吃”只可能发生在行或列的中间位置。具体来说，一个棋子被夹吃，必然是以下两种模式之一：

横向：o*o (小红的棋子被吃) 或 *o* (小紫的棋子被吃)。
纵向：三行中同一列构成了 o*o 或 *o* 的模式。

我们可以设置两个布尔变量，kou_eaten 和 yukari_eaten，分别记录小红和小紫是否有棋子被吃。

算法步骤如下：

循环 $t$ 次处理每组测试数据。
在每次循环中，读入一个 $3 \cdot 3$ 的棋盘。
初始化 kou_eaten = false 和 yukari_eaten = false。
检查所有行：遍历棋盘的第0、1、2行。检查是否存在 o*o 或 *o* 的情况。如果找到，相应地更新布尔变量。
检查所有列：遍历棋盘的第0、1、2列。检查是否存在 o*o 或 *o* 的情况。如果找到，相应地更新布尔变量。
遍历结束后，根据两个布尔变量的值判断胜负：
- 如果 kou_eaten 为真且 yukari_eaten 为假，说明只有小红被吃，小紫胜。
- 如果 kou_eaten 为假且 yukari_eaten 为真，说明只有小紫被吃，小红胜。
- 其他所有情况（双方都被吃或双方都未被吃），均为平局。

代码

c++
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][0] == 'o' && board[i][1] == '*' && board[i][2] == 'o') {
            kou_eaten = true;
        }
        if (board[i][0] == '*' && board[i][1] == 'o' && board[i][2] == '*') {
            yukari_eaten = true;
        }
    }

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

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

int main() {
    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 kou_eaten = false;
        boolean yukari_eaten = false;

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

        // 检查列
        for (int j = 0; j < 3; j++) {
            if (board[0][j] == 'o' && board[1][j] == '*' && board[2][j] == 'o') {
                kou_eaten = true;
            }
            if (board[0][j] == '*' && board[1][j] == 'o' && board[2][j] == '*') {
                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 \cdot 3$ 棋盘进行常数次检查（3行3列），所以处理单个棋盘的时间是 $O(1)$ 。总时间复杂度为 $O(t)$ ，其中 $t$ 是询问次数。
空间复杂度：对于每组测试用例，我们使用一个 $3 \cdot 3$ 的数组来存储棋盘，所需空间是 $O(1)$ 。总空间复杂度为 $O(1)$ 。