小米笔试 小米笔试题 20260314

笔试时间：2026年3月14日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：农田改造

题目

某地区有一片 n×m 的农田网格，每个格子要么是 "旱田"（用 x 表示，无法通水），要么是 "水田"（用 o 表示，可以通水）。水利部门计划对部分旱田进行改造，他们只能选择其中一块旱田，将其改造成水田。

水利部门定义 "连通水田块" 指的是四连通区域（即区域内的任意两块水田可通过上下左右移动仅经过区域内的水田互相到达），"最大连通水田块" 是指该区域在所有可能的连通水田块中面积最大（格子数量最多）。

水利部门希望先计算出不同选择后能形成的最大连通水田块的情况后再实施改造。请针对网格中的每个格子输出结果：

• 若该格子原本是水田，输出 0；
• 若原本是旱田，输出将该位置改造成水田后，包含该位置的最大连通水田块的大小。

输入描述

第一行包含两个正整数 n 和 m，表示农田网格的行数和列数。接下来 n 行，每行包含一个长度为 m 的字符串，字符串由 x（旱田）和 o（水田）组成，描述农田网格的初始状态。

数据范围

1 ≤ n, m ≤ 500

输出描述

输出 n 行，每行 m 个整数，中间用空格隔开。对于原本是水田的格子，输出 0；对于原本是旱田的格子，输出将该位置改造成水田后，包含该位置的最大连通水田块的大小。

样例输入1

3 3
xoo
oxo
xox

样例输出1

5 0 0
0 6 0
3 0 5

样例输入2

6 5
ooooo
oxxoo
xxxox
oxxoo
xooxx
ooooo

样例输出2

0 0 0 0 0
0 12 12 0 0
13 1 12 0 12
0 9 19 0 0
9 0 0 19 19
0 0 0 0 0

参考题解

解题思路：

BFS 连通块染色 + 四向枚举。

直接先把所有 o 的连通块编号并统计大小，然后每个 x 看四个方向能连到哪些不同的水田连通块，答案就是 1 + 这些连通块大小之和。

C++

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; i++) cin >> g[i];
    
    vector<vector<int>> id(n, vector<int>(m, -1));
    vector<int> siz;
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] != 'o' || id[i][j] != -1) continue;
            int cur = siz.size();
            queue<pair<int, int>> q;
            q.push({i, j});
            id[i][j] = cur;
            int cnt = 0;
            while (!q.empty()) {
                auto t = q.front();
                q.pop();
                int x = t.first, y = t.second;
                cnt++;
                for (int k = 0; k < 4; k++) {
                    int a = x + dx[k], b = y + dy[k];
                    if (a < 0 || a >= n || b < 0 || b >= m) continue;
                    if (g[a][b] != 'o' || id[a][b] != -1) continue;
                    id[a][b] = cur;
                    q.push({a, b});
                }
            }
            siz.push_back(cnt);
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int res = 0;
            if (g[i][j] == 'x') {
                res = 1;
                int st[4], top = 0;
                for (int k = 0; k < 4; k++) {
                    int a = i + dx[k], b = j + dy[k];
                    if (a < 0 || a >= n || b < 0 || b >= m) continue;
                    if (g[a][b] != 'o') continue;
                    int t = id[a][b];
                    bool ok = true;
                    for (int u = 0; u < top; u++) {
                        if (st[u] == t) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) {
                        st[top++] = t;
                        res += siz[t];
                    }
                }
            }
            cout << res << (j + 1 == m ? '\n' : ' ');
        }
    }
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        String[] g = new String[n];
        for (int i = 0; i < n; i++) g[i] = br.readLine();
        
        int[][] id = new int[n][m];
        for (int[] row : id) Arrays.fill(row, -1);
        List<Integer> siz = new ArrayList<>();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i].charAt(j) != 'o' || id[i][j] != -1) continue;
                int cur = siz.size();
                Queue<int[]> q = new LinkedList<>();
                q.offer(new int[]{i, j});
                id[i][j] = cur;
                int cnt = 0;
                while (!q.isEmpty()) {
                    int[] t = q.poll();
                    int x = t[0], y = t[1];
                    cnt++;
                    for (i