解题思路
把原图中所有红色格子看成点,按上下左右四个方向连边。题目要求对每个位置 (i,j),把它染成白色后,求剩余红色连通块个数。
核心结论如下:
- 如果原来这个位置就是白色,那么染成白色后图不变,答案就是原图红色连通块总数。
- 如果原来这个位置是红色,那么相当于删除这个红点,删除后红色连通块数会发生变化。
P1147.第1题-又一个连通块数数题
前言
第一题太水了,群友已经忘记内容了。想必应该也是个人均都会的签到题。大家从第二题开始看吧
题目内容
小红是一个年轻的程序员,他热爱计算机科学和数学。他一直在思考如何利用计算机技术来解决实际问题。有一天,他接到了一项任务,要为一个遥远的星球上的一座城市设计一个城市规划系统。
这个城市非常大,由许多小区域组成。每个小区域都有一个 n∗m 的矩阵,矩阵中的每个位置都取值为 W 或 R,分别代表白色和红色。这些小区域之间可能存在道路或其他障碍物,但每个小区域内部都是连通的。
小红想知道,如果将任意位置 (i,j) 涂成白色后,会有多少个全红的连通块,求一个 n∗m 的矩阵 ans , ans[i][j] 表示将位置 (i,j) 涂成白色以后,剩下的全红连通块个数。 保证数据随机生成
输入描述
第一行为两个整数 n 和 m ,( 1≤n,m≤40 )
接下来 n 行,每行有 m 个字母,每个字母取值为 W 或 R 。
输出描述
输出为一个 n∗m 的矩阵。
样例
输入
4 3
R W W
W R R
R R R
W W W
输出
1 2 2
2 2 2
2 3 2
2 2 2