笔试时间：2025年9月20日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：围棋决策

题目描述：小强最近在研究围棋，他希望有一个程序能告诉他一步之内，有哪些位置可以直接吃掉别人的棋子，吃几个。

围棋可以在围住别人的情况下，吃掉别人的棋子。标准围棋的棋盘是19×19的，但小强只是想研究围棋的规则，故假定棋盘大小为n×n。

围棋吃子的规则：

• 敌方的棋子里，上下左右直接相邻的棋子视为连通。
• 若我方落子后，对方有一个连通块中，所有棋子的上下左右四个格子都没有空格（即或为我方的棋子，或为边界，或为敌人的棋子时），该部分棋子被视为吃掉。

输入描述

第一行输入一个整数 n（5 ≤ n ≤ 1000），表示棋盘的大小是 n×n 的。

随后 n 行，每行 n 个字符：

• '.' 表示该位置没有棋子
• 'x' 表示该位置是敌方棋子
• 'o' 表示该位置是我方棋子

下一步只能在 '.' 的位置落子。

数据保证初始局面不会有相互吃的情况，即初始局面合法。

输出描述

若有 k 个位置落子可以吃掉至少一个敌方棋子：

• 第一行输出一个整数 k。
• 随后 k 行，每行输出 a_i, b_i, c_i，分别表示横坐标、纵坐标和个数。

输出要求：

• 按 a_i 从小到大的顺序输出
• 当 a_i 相同时，按照 b_i 从小到大输出

样例输入

6

.oo.o.

oxxox.

ox.xox

xoxoox

xoo...

.x..ox

样例输出

4

2 6 1

3 3 5

5 6 1

6 1 2

样例说明：有 4 个位置可以吃掉对手的棋子：

• 置于 (2,6) 可以吃掉棋子 (2,5)。
• 置于 (3,3) 可以吃掉棋子 (2,2), (2,3), (3,2), (3,4), (4,3)。
• 置于 (5,6) 可以吃掉棋子 (6,6)。
• 置于 (6,1) 可以吃掉棋子 (4,1) 和 (5,1)。

参考题解

解题思路：

1. 使用BFS/DFS遍历所有敌方棋子'x'，找出它们的连通块（上下左右相邻即连通）。
2. 每个连通块记录：大小（棋子数）和气（相邻的空位集合）。
3. 若某个敌方连通块只有一个气，说明只要在这个空位落子，就能吃掉整个连通块。
4. 统计所有可吃子的落子位置，并按坐标排序输出。

C++：

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

int n;
vector<vector<char>> board;
vector<vector<int>> vis;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

struct Comp {
    int size;
    set<string> liberties;
};

int main() {
    cin >> n;
    board.resize(n, vector<char>(n));
    vis.resize(n, vector<int>(n, 0));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    
    int compId = 0;
    vector<Comp> comps;
    
    // 找敌方连通块
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'x' && vis[i][j] == 0) {
                compId++;
                queue<pair<int, int>> q;
                q.push({i, j});
                vis[i][j] = compId;
                int sz = 0;
                set<string> libs;
                
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    sz++;
                    
                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                        if (board[nx][ny] == 'x' && vis[nx][ny] == 0) {
                            vis[nx][ny] = compId;
                            q.push({nx, ny});
                        } else if (board[nx][ny] == '.') {
                            libs.insert(to_string(nx) + "," + to_string(ny));
                        }
                    }
                }
                comps.push_back({sz, libs});
            }
        }
    }
    
    // 记录每个空位能吃多少
    map<string, int> eat;
    for (auto& comp : comps) {
        if (comp.liberties.size() == 1) {
            string pos = *comp.liberties.begin();
            eat[pos] = eat[pos] + comp.size;
        }
    }
    
    // 整理结果
    vector<vector<int>> ans;
    for (auto& [pos, cnt] : eat) {
        int comma = pos.find(',');
        int x = stoi(pos.substr(0, comma));
        int y = stoi(pos.substr(comma + 1));
        ans.push_back({x + 1, y + 1, cnt}); // 坐标从1开始
    }
    
    sort(ans.begin(), ans.end());
    
    // 输出
    cout << ans.size() << endl;
    for (auto& arr : ans) {
        cout << arr[0] << " " << arr[1] << " " << arr[2] << endl;
    }
    
    return 0;
}

Java：

import java.util.*;

public class Main {
    static int n;
    static char[][] board;
    static int[][] vis;
    static final int[] dx = {1, -1, 0, 0};
    static final int[] dy = {0, 0, 1, -1};
    
    static class Comp {
        int size;
        Set<String> liberties;
        Comp(int size, Set<String> liberties) {
            this.size = size;
            this.liberties = liberties;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        board = new char[n][n];
        for (int i = 0; i < n; i++) {
            board[i] = sc.next().toCharArray();
        }
        
        vis = new int[n][n];
        int compId = 0;
        List<Comp> comps = new ArrayList<>();
        
        // 找敌方连通块
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'x' && vis[i][j] == 0) {
                    compId++;
                    Queue<int[]> q = new LinkedList<>();
                    q.add(new int[]{i, j});
                    vis[i][j] = compId;
                    int sz = 0;
                    Set<String> libs = new HashSet<>();
                    
                    while (!q.isEmpty()) {
                        int[] cur = q.poll();
                        int x = cur[0], y = cur[1];
                        sz++;
                        
                        for (int d = 0; d < 4; d++) {
                            int nx = x + dx[d], ny = y + dy[d];
                            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                            if (board[nx][ny] == 'x' && vis[nx][ny] == 0) {
                                vis[nx][ny] = compId;
                                q.add(new int[]{nx, ny});
                            } else if (board[nx][ny] == '.') {
                                libs.add(nx + "," + ny);
                            }
                        }
                    }
                    comps.add(new Comp(sz, libs));
                }
            }
        }
        
        // 记录每个空位能吃多少
        Map<String, Integer> eat = new HashMap<>();
        for (Comp comp : comps) {
            if (comp.liberties.size() == 1) {
                String pos = comp.liberties.iterator().n