题面描述

存在一个 $m \times n$ 的二维数组，其元素取值为 $0$、$1$ 或 $2$。

• 值为 $1$ 的元素具有同化特性，每经过 $1$ 秒，将其上下左右（四个方向）值为 $0$ 的元素同化为 $1$。
• 值为 $2$ 的元素对同化免疫，不会被同化。

初始时，数组中的所有元素随机被初始化为 $0$ 或 $2$，然后将矩阵的左上角元素 $[0, 0]$ 修改为 $1$。经过足够长的时间后，求矩阵中值为 $0$ 或 $2$ 的元素个数。

思路

本题可以看作是一个广度优先搜索（BFS）的问题，模拟同化过程。具体步骤如下：

1. 初始化：将所有元素初始化为 $0$ 或 $2$，然后将起始位置 $(0,0)$ 设置为 $1$。
2. 同化过程：
   • 使用队列来记录当前被同化的元素位置。
   • 每次从队列中取出一个位置，尝试将其上下左右的 $0$ 元素同化为 $1$，并将新同化的位置加入队列。
   • 由于 $2$ 是免疫的，因此在同化过程中遇到 $2$ 时跳过。
3. 统计结果：在同化过程结束后，遍历整个矩阵，统计值为 $0$ 或 $2$ 的元素个数。

cpp

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

int main(){
    int m, n;
    cin >> m >> n;
    // 初始化矩阵
    vector<vector<int>> grid(m, vector<int>(n));
    for(int i=0;i<m;i++) {
        for(int j=0; j<n; j++) {
            cin >> grid[i][j];
        }
    }
    // 将起始位置设为1
    grid[0][0] = 1;
    // 定义方向数组：上、下、左、右
    vector<pair<int, int>> directions = { {-1,0}, {1,0}, {0,-1}, {0,1} };
    // BFS队列
    queue<pair<int, int>> q;
    q.push({0, 0});
    while(!q.empty()){
        pair<int, int> current = q.front(); q.pop();
        int x = current.first, y = current.second;
        // 遍历四个方向
        for(auto &dir : directions){
            int nx = x + dir.first, ny = y + dir.second;
            // 检查边界
            if(nx >=0 && nx < m && ny >=0 && ny < n){
                // 如果是0，则同化为1并加入队列
                if(grid[nx][ny] == 0){
                    grid[nx][ny] = 1;
                    q.push({nx, ny});
                }
                // 如果是2，则跳过
            }
        }
    }
    // 统计非1的元素
    int count = 0;
    for(int i=0;i<m;i++) {
        for(int j=0; j<n; j++) {
            if(grid[i][j] != 1) count++;
        }
    }
    cout << count;
    return 0;
}

python

from collections import deque

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    m, n = int(data[0]), int(data[1])
    grid = []
    idx = 2
    for _ in range(m):
        row = []
        for _ in range(n):
            row.append(int(data[idx]))
            idx +=1
        grid.append(row)
    # 将起始位置设为1
    grid[0][0] =1
    # 定义四个方向：上、下、左、右
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    # BFS队列
    q = deque()
    q.append((0,0))
    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            # 检查边界
            if 0 <= nx < m and 0 <= ny < n:
                if grid[nx][ny] ==0:
                    grid[nx][ny] =1
                    q.append((nx, ny))
    # 统计非1的元素
    count = 0
    for row in grid:
        for val in row:
            if val !=1:
                count +=1
    print(count)

if __name__ == "__main__":
    main()

java

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[][] grid = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                grid[i][j] = sc.nextInt();
            }
        }
        // 将起始位置设为1
        grid[0][0] =1;
        // 定义四个方向：上、下、左、右
        int[][] directions = { {-1,0}, {1,0}, {0,-1}, {0,1} };
        // BFS队列
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0,0});
        while(!q.isEmpty()){
            int[] current = q.poll();
            int x = current[0], y = current[1];
            for(int[] dir : directions){
                int nx = x + dir[0], ny = y + dir[1];
                // 检查边界
                if(nx >=0 && nx < m && ny >=0 && ny < n){
                    if(grid[nx][ny] ==0){
                        grid[nx][ny] =1;
                        q.offer(new int[]{nx, ny});
                    }
                    // 如果是2，则跳过
                }
            }
        }
        // 统计非1的元素
        int count =0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j] !=1) count++;
            }
        }
        System.out.println(count);
    }
}

题目描述

存在一个 $m*n$ 的二维数组，其成员取值范围为 $0$，$1$，$2$。

其中值为 $1$ 的元素具备同化特性，每经过 $1S$，将上下左右值为 $0$ 的元素同化为 $1$ 。

而值为 $2$ 的元素，免疫同化。

将数组所有成员随机初始化为 $0$ 或 $2$， 再将矩阵的 $[0, 0]$ 元素修改成 $1$ ，在经过足够长的时间后求矩阵中有多少个元素是 $0$ 或 $2$（即 $0$ 和 $2$ 数量之和）。

输入描述

输入的前两个数字是矩阵大小。后面是数字矩阵内容。

输出描述

返回矩阵中非 $1$ 的元素个数。

样例1

输入

4 4
0 0 0 0
0 2 2 2
0 2 0 0
0 2 0 0

输出

9

说明

输入数字前两个数字是矩阵大小。后面的数字是矩阵内容。 起始位置($0,0$)被修改为 $1$ 后，最终只能同化矩阵为：

1 1 1 1

1 2 2 2

1 2 0 0

1 2 0 0

所以矩阵中非 $1$ 的元素个数为 $9$