首页 > 试题广场 >

地、颜色、魔法

[编程题]地、颜色、魔法
红色来源于山脉,象征着狂躁、愤怒、混乱,血雨腥风,电光火石。
蓝色来源于海岛,象征着控制、幻觉、诡计,运筹帷幄,谋定后动。
绿色来源于树林,象征着生命、蛮力、成长,横冲直撞,生生不息。
黑色来源于沼泽,象征着死亡、贪婪、腐败,追求卓越,不计代价。
白色来源于平原,象征着秩序、公平、正义,携手共进,稳中求胜。

       现在,你作为一名新星鹏洛客,找到了一块绝佳的修炼地。这块地方可以被描述成一个 n x m 的矩形。你已经在这块地中的一些位置打好了标记。接下去,就该对整块地赋予你的颜色了。一个位置能被赋予你的颜色,当且仅当满足以下条件之一:
       1. 这个位置被打上了标记。
       2. 这个位置在不经过被打标记的位置的情况下与边界不连通(这个图是四联通的)。换句话说,如果你从这个位置开始,在不经过被打标记的位置,且只能向上下左右四个方向移动的情况下永远不能走到地图的边界,那么这个位置符合条件。
       现在,你的好基友想知道,你能为多少个位置赋予你自己的颜色呢?

输入描述:
第一行包含两个正整数 n, m ,表示地图的长和宽。
接下去 n 行,每行一个长为 m 的字符串,表示地图的一行。
其中  表示该位置未被打标记; 表示该位置被打了标记。
保证地图仅由  和  构成。


输出描述:
输出仅一行,包含一个整数,表示你的答案。
示例1

输入

4 4
....
.###
.#.#
.###

输出

9

说明

可以被赋予颜色的位置在下图中用  标出了。
\texttt{....}
\texttt{.@@@}
\texttt{.@@@}
\texttt{.@@@}

备注:
1 ≤ n x m ≤ 106
头像 Clouder0
发表于 2020-08-11 23:41:52
E 看上去就很水的题目,然而给的限制是 导致必须使用 vector 存图,于是频繁出锅,卡了我很久。一开始使用并查集做法,具体思路如下:使用维护 的并查集,将边界放在同一集合中,将 # 点看做障碍,每个 . 点四方向合并集合,最后统计非边界集合的大小和,加上 # 点数量即为答案。由于不明原因锅了 展开全文
头像 耕云种月
发表于 2022-01-30 16:24:01
原题解链接:https://ac.nowcoder.com/discuss/150009 从地图边界开始DFSDFSDFS,在不经过#的情况下所能到达的所有点都是不合法的。那么记能到达的点数为cntcntcnt,答案即为nxm−cntnx m- cntnxm−cnt。 注意所有的#都是要被计人答案的 展开全文
头像 JiayinDeng
发表于 2020-08-13 09:18:52
E 题解 看到大部分人都是dfs或bfs搜索做的,这里给一个并查集的方法:对于边缘处的'.',与一个extra=m*n连接;对于不在边缘处的'.',merge其上下左右的'.'和该点。最后遍历,遍历到不与extra连通的'.',ans++。再把'#'加到答案中, 代码 #include<bit 展开全文
头像 996使我快乐!!!
发表于 2020-07-13 08:08:06
注意不要越界,用string【】代替char【】 #include<iostream> #include<string.h> #include<stack> #include<vector> #include<algorithm> #inc 展开全文
头像 九天之月_柔骨魅兔
发表于 2025-10-25 14:43:30
#include<stdio.h> #include<math.h> int main(){ int n; int arr[2000000];//规定可接受长度; int fen;//定义每个人的分数; int xiao;//求取小于你的值;为后续的对数提供数值 int hu 展开全文