朴素的求连通块个数。两遍dfs,一次正常算,一次把Y,Z看作一样的字符算。做差即可。
C++
一位研究员正在处理一个 n 行 m 列的符号矩阵,每个位置写有 R、G、B 三种符号之一。正常处理时,两个相邻位置若符号相同,则属于同一个连通块;这里的相邻指上下左右四个方向。
研究员使用的分析设备存在故障:它会将 G 和 B 误认为同一种符号,但 R 不会被其他符号合并。因此,在设备视角中,任意一个 G 或 B 位置与相邻的 G 或 B 位置都会被看作连通。
现在需要计算:设备视角下的连通块数量比正常处理时的连通块数量少了多少。
矩阵的行数 n 和列数 m 都至少为 1,且不超过 1000。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册