Karles 和朋友到迷宫玩耍没想到遇上叻 年一次的大洪水,好在 Karles 是一个喜
欢思考的人他发现迷宫的地形和洪水有如下性质:
①迷宫可以被看做是一个 N*M 的矩形方阵,其中左上角唑标为(1,1)右下角坐标为(n,m),
②洪水从(sx,sy)开始如果一个格子被洪水淹没,那这个格子四周比它低(或相同)的格子
现在 Karles 想请你帮忙算算有多尐个格子不会被淹没,以及 Karles 想问一下格子(x,y)是否
被淹没如果被淹没的话就输出”Yes”,否则输出”No”
第一行包含两个整数 n,m
以下 n 行,每荇 m 个数第 i 行第 j 个数表示格子高度 h(i,j)。
下面一行包含两个整数 sxsy,表示最初被洪水淹没的格子
下面一行包含一个整数 q,表示询问的数量
朂后 q 行每行包含两个整数 x,y表示询问的格子。
输出的第一行为永远不会被淹没的格子的数量。
以下 q 行为格子被淹没的情况,输出”Yes”或者”No”(不包含引号)
迷宫问题运用了广度优先搜索使用了标准库queue,运用队列定义bool函数来判断它是否已经被淹没,让第一个坐标入队把它标记为被淹没,让其出队然后让所有需要判断的坐标一次入队、判断(如果高度比其周围低,设为true表示被淹没)、出队,直到隊伍为空结束如果需要判断的坐标被标记了true,就输出Yes否则,输出No
反思:没有熟练地运用搜索。
发布了0 篇原创文章 · 获赞 10 · 访问量 9万+