题目链接
https://ac.nowcoder.com/acm/problem/20898
分析题目
说好懂也好懂，说不好理解也确实不好理解。
其实就是，跟围棋差不多，被'#'围住的都属于'#'的势力范围，而那些和边界相连的'.'则不属于'#'的势力范围。题目要求'#'的势力范围。
解题思路
如果我们的思路是遍历全部点，若为'.'，从此处开始dfs/bfs，相连通的'.'都和最初开始的'.'的属性是一样的，就是说凡是dfs/bfs路径上遇到的'.'要么全是属于'#'势力范围的，要么就都不属于。当dfs/bfs到边界点的时候，开始返回，路径上的点全部标记一下不属于'#'势力范围；当dfs/bfs无法到达边界点的时候，不进行标记，路径上的点属于'#'势力范围。（有时间的话我打算写写试试）
另辟蹊径，与边界相连的连通区域是不属于'#'势力范围的。因此，我们不妨从边界'.'开始遍历，遇到的'.'必然是不属于'#'势力范围的，而没遇到的都是'#'势力范围的。我们把遇到的点都标记一下，最后遍历一遍整个图，统计未被标记点的个数，就是答案。
AC代码
//比较特殊的一点是，我用的二维数组编号进行存储的。因为直接用二维数组是开不下的。可以用vector或者string等等。
//这里不想再写一遍了，大家可以去这个题解里找一下二维数组编号的知识，挺明显的。
//https://blog.nowcoder.net/n/d18e6ea8503841f1a215250657a799cc
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int mp[N];//0代表'#'，1代表'.'，2代表标记不属于'#'势力范围
int n,m;
int vis[N];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void dfs(int x,int y){//类似dfs板子，稍微变了点
mp[x*m+y]=2;//凡是能连通的'.'都赋值为2，进行标记
for(int k=0;k<4;k++){
int tx=x+dir[k][0],ty=y+dir[k][1];
if(tx>=n||ty>=m||tx<0||ty<0) continue;
if(mp[tx*m+ty]==1){//是 '.' 的情况才能进行
vis[tx*m+ty]=1;
dfs(tx,ty);
vis[tx*m+ty]=0;
}
}
}
int main(){
char ch;
cin>>n>>m;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
scanf(" %c",&ch);//这样能滤去空格、tab和回车
if(ch=='#') mp[i*m+j]=0;
if(ch=='.') mp[i*m+j]=1;
}
for(int i=0;i<n;i++){//遍历左边界右边界
if(mp[i*m+0]==1) {dfs(i,0);vis[i*m+0]=1;}
if(mp[i*m+m-1]==1) {dfs(i,m-1);vis[i*m+m-1]=1;}
}
for(int i=0;i<m;i++){//遍历上边界下边界
if(mp[0*m+i]==1) {dfs(0,i);vis[0*m+i]=1;}
if(mp[(n-1)*m+i]) {dfs(n-1,i);vis[(n-1)*m+i]=1;}
}
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(mp[i*m+j]!=2)//没被标记的就是'#'的势力范围
ans++;
cout<<ans;
}哔哔赖赖
我没做出来，因为用遍历所有'.'的方法实在没想过来，明天我试着再写写。
看着比赛中的大佬半小时解决这个题，我花了俩小时都没做对。555555QWQ
也学到了新思路，算是潜移默化的影响了一点，不亏！
最后的最后，我还想问上天一句：我什么时候才能成为大佬啊啊啊！！！
京公网安备 11010502036488号