洛谷 P1596 [USACO10OCT] Lake Counting S 刷题条记
P1596 Lake Counting S - 洛谷 | 计算机科学教诲新生态https://i-blog.csdnimg.cn/direct/3dde20edbc0344469af5b6d701282e04.png
一道判断有多少个联通块的问题
观察 对于水来说 其八个方向相邻都属于同一个联通块
我们可以存水的位置 搜刮每个水可以到达的所有位置
将搜过的位置标记为陆地避免重复搜刮
搜完答案数+1
完整代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=110;
char a={'.'};
bool b;
int c;
int dir[]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int ans = 0;
void dfs(int x,int y){
for(int i = 0;i < 8;i++)
{
int dx = x +dir;
int dy = y +dir;//搜刮八个方向
if(a=='W'&&dx>0&&dx<=n&&dy>0&&dy<=m)
//假如下个位置为水且没有越界
{
a ='.';//标记为陆地 核心
dfs(dx,dy);
}
}
}
int main(){
cin>>n>>m;
int maxx = max(n,m);
for(int i = 0 ;i <= maxx;i++){
/*b = true;
b = true;
b = true;
b = true;*/
a = '.';//将四条边界标记为陆地
a = '.';
a = '.';
a = '.';
}
int cnt = 0;
for(int i = 1;i <= n ; i++){
for(int j = 1;j <= m; j++){
cin>>a;
if(a=='W'){
c = i;
c = j;
cnt++;
}
}
}
int step = 0;
while(cnt){
if(a]] == 'W'){
//有可能当前位置的水与前面搜刮的水联通被记为了陆地 以是要先判断一下
//确定当前是一块未被搜刮过的 新 水
dfs(c,c);
ans++;//联通块个数加一
}
step++;//搜刮下一个位置
cnt--;
}
cout<<ans;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]