分析 网站,房屋平面图设计app,室内设计公司官网,wordpress 用户 表单文章目录 分值#xff1a;200题目描述思路复杂度分析AC 代码 分值#xff1a;200
题目描述
存在一个 m * n 的 二维数组只#xff0c;其成员取值范围为0, 1, 2。其中值为1的元素具备同化特性#xff0c;每经过1S#xff0c;将上下左右值为0的元素同化为1。而值为2的元素… 文章目录 分值200题目描述思路复杂度分析AC 代码 分值200
题目描述
存在一个 m * n 的 二维数组只其成员取值范围为0, 1, 2。其中值为1的元素具备同化特性每经过1S将上下左右值为0的元素同化为1。而值为2的元素免疫同化。 将数组所有成员随机初始化只为0或2再将矩阵的[0,0]元素修改成1在经过足够长的时间后求矩阵中有多少个元素是0或2(即0和2数量之和)。 输入描述: 输入的前两个数字是矩阵大小n 和m。 接着输入n行m列表示矩阵信息。 输出描述: 返回矩阵中非 1的元素个数。 示例1 输入 4 4 0 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2 输出 3 解释 除了矩阵中 3 个值为2的元素其他元素全部同化为1了。 示例2 输入 4 4 0 2 0 0 0 2 0 0 0 2 0 0 0 2 0 0 输出 12 解释 只有第一列被同化为1了第2、3、4列没有被同化因为第二列全是值为2的元素阻挡住同化了。 Tips:
0 m, n 30
思路
从将上下左右值为0的元素同化为1 这点可以联系到BFS这是一道很经典的宽度优先搜索的题目可以当做模板题进行练习。从[0, 0]开始出发只有值为0的元素才能被同化所以只将1周围的 0 元素放进队列直到队列为空即可。答案要求返回矩阵中非 1的元素个数。可以在遍历的同时进行计算每当有一个元素被同化那么ans就减一。
复杂度分析
时间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)其中N和M分别为矩阵的行长跟列长每个位置只需要访问一次。空间复杂度 O ( n ∗ m ) O(n*m) O(n∗m)其中N和M分别为矩阵的行长跟列长用于存储矩阵信息。
AC 代码
C 版
#include bits/stdc.h
using namespace std;
int main()
{int n, m, ans, dis[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};cin n m;vectorvectorint mx(n, vectorint(m));for (int i 0; i n; i){for (int j 0; j m; j){cin mx[i][j];}}mx[0][0] 1;// 一开始 0 跟 2 的个数之和, 后面每次有同化的就 -1 即可ans n * m - 1;queuepairint, int q;q.push({0, 0});while (!q.empty()){auto t q.front();q.pop();for (int i 0; i 4; i){int x t.first dis[i][0], y t.second dis[i][1];if (x 0 x n y 0 y m mx[x][y] 0){mx[x][y] 1;ans--;q.push({x, y});}}}cout ans endl;return 0;
}JAVA 版
import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();int ans;int[][] dis {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int[][] mx new int[n][m];for (int i 0; i n; i) {for (int j 0; j m; j) {mx[i][j] scanner.nextInt();}}mx[0][0] 1;ans n * m - 1;Queueint[] q new LinkedList();q.add(new int[]{0, 0});while (!q.isEmpty()) {int[] t q.poll();for (int i 0; i 4; i) {int x t[0] dis[i][0];int y t[1] dis[i][1];if (x 0 x n y 0 y m mx[x][y] 0) {mx[x][y] 1;ans--;q.add(new int[]{x, y});}}}System.out.println(ans);}
}Python 版
from collections import dequen, m map(int, input().split())
ans 0
dis [[-1, 0], [1, 0], [0, -1], [0, 1]]mx []
for _ in range(n):mx.append(list(map(int, input().split())))mx[0][0] 1
ans n * m - 1
q deque([(0, 0)])while q:t q.popleft()for i in range(4):x t[0] dis[i][0]y t[1] dis[i][1]if 0 x n and 0 y m and mx[x][y] 0:mx[x][y] 1ans - 1q.append((x, y))print(ans)
