#P3202. 数值同化(200分)
-
1000ms
Tried: 55
Accepted: 30
Difficulty: 3
所属公司 :
华为od
数值同化(200分)
题面描述
存在一个 m×n 的二维数组,其元素取值为 0、1 或 2。
- 值为 1 的元素具有同化特性,每经过 1 秒,将其上下左右(四个方向)值为 0 的元素同化为 1。
- 值为 2 的元素对同化免疫,不会被同化。
初始时,数组中的所有元素随机被初始化为 0 或 2,然后将矩阵的左上角元素 [0,0] 修改为 1。经过足够长的时间后,求矩阵中值为 0 或 2 的元素个数。
思路
本题可以看作是一个广度优先搜索(BFS)的问题,模拟同化过程。具体步骤如下:
- 初始化:将所有元素初始化为 0 或 2,然后将起始位置 (0,0) 设置为 1。
- 同化过程:
- 使用队列来记录当前被同化的元素位置。
- 每次从队列中取出一个位置,尝试将其上下左右的 0 元素同化为 1,并将新同化的位置加入队列。
- 由于 2 是免疫的,因此在同化过程中遇到 2 时跳过。
- 统计结果:在同化过程结束后,遍历整个矩阵,统计值为 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