赞
踩
获取题库不需要订阅专栏,可直接私信我进入CSDN领军人物top1博主的华为OD交流圈观看完整题库、最新面试实况、考试报告等内容以及大佬一对一答疑。
题目描述
在一个地图中(地图由n*n个区域组成),有部分区域被感染病菌。 感染区域每天都会把周围(上下左右)的4个区域感染。 请根据给定的地图计算,多少天以后,全部区域都会被感染。 如果初始地图上所有区域全部都被感染,或者没有被感染区域,返回-1
输入描述
一行N*N个数字(只包含0,1,不会有其他数字)表示一个地图,数字间用,分割,0表示未感染区域,1表示已经感染区域 每N个数字表示地图中一行,输入数据共表示N行N列的区域地图。
例如输入1,0,1,0,0,0,1,0,1,表示地图
1,0,1
0,0,0
1,0,1
输出描述
一个整数,表示经过多少天以后,全部区域都被感染 1<=N<200
题目解析
本题是一个典型的广度优先搜索(BFS)问题。我们需要从所有已感染的区域(值为1的格子)开始,使用BFS搜索它们周围的未感染区域(值为0的格子),并将这些未感染区域标记为已感染(即将值从0变为1)。每天我们都重复这个过程,直到所有区域都被感染或无法再感染新的区域为止。
需要注意的是,如果初始地图上所有区域都已经被感染(即没有值为0的格子)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。