解题思路: 1.经典的BFS/DFS问题.
2.与 第2171题:细胞 差不多,但是由于我那个题用的DFS,所以这个题就用BFS.
多说一点:1.DFS的递归函数可以很简单地编写,也更清晰明了,所以更适合解决这种搜索问题.
2.并且BFS因为需要将每个状态依次加入队列中(这里是坐标),所以需要与状态数成正比的内存空间,
而DFS需要的内存空间与递归深度成正比,而一般情况下递归深度要低于状态数,所以可以认为DFS更省空间
3.求最短路径经常使用DFS
注意事项:1.是八个方向,不要弄成四个了.
参考代码:
#include<bits/stdc++.h> using namespace std; int N,M; int i,j,k; char E[1005][115]; //记录地图 int book[1005][115]; //记录是否走过 pair<int,int> loc,temp; //用于记录坐标 queue< pair<int,int> > que; //坐标队列 int cnt; //用于统计水坑数量 int Next[8][2] = {{0,-1},{-1,0},{0,1},{1,0},{-1,-1},{1,-1},{-1,1},{1,1}}; //对应八个方向 int nx,ny; //下一步的坐标 int main() { scanf("%d %d",&N,&M); //读入地图 for(i = 1; i <= N; i++) { scanf("%s",&E[i][1]); } //遍历地图 for(i = 1; i <= N;i++) { for(j = 1; j <= M; j++) { //如果找到了水坑,就把它变成干燥处,然后纳入队列中,同时总水坑数量加一 if(E[i][j] == 'W' && book[i][j] == 0) { cnt++; book[i][j] = 1; E[i][j] = '.'; //用pair类型的变量loc记录坐标加入队列中 loc.first = i; loc.second = j; que.push(loc); //当队列不为空就一直循环 while(que.empty() != 1) { //首先从队列中取一个元素出来给loc,然后就让他pop出队列 loc = que.front(); que.pop(); for(k = 0; k <= 7; k++) { //看是否有八连通的积水 nx = loc.first + Next[k][0]; ny = loc.second + Next[k][1]; //如果有的话,就入队,准备进行再一次的BFS if(nx >=1 && nx <= N && ny >= 1 && ny <= M &&//判断是否出界 book[nx][ny] == 0 && E[nx][ny] == 'W')//判断是否是水,且没有走过 { //先标记为走过,然后把它变成高早出,再入队 book[nx][ny] = 1; E[nx][ny] = '.'; //用临时pair变量temp来储存坐标 temp.first = nx; temp.second = ny; que.push(temp); } } } } } } /*八连通的水'W' 会在一个while里全部变成干燥处'.', 也就是说,外面两层for循环能够遍历到的水'W'的个数,就是水洼的个数*/ cout << cnt; return 0; }
0.0分
1 人评分
C语言训练-字符串正反连接 (C语言代码)浏览:618 |
C语言程序设计教程(第三版)课后习题8.9 (Java代码)浏览:1325 |
A+B for Input-Output Practice (III) (C语言代码)浏览:419 |
删除数组中的0元素 (C语言代码)浏览:2023 |
C语言程序设计教程(第三版)课后习题8.4 (C++代码)浏览:444 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:509 |
【亲和数】 (C语言代码)浏览:688 |
Manchester-台球碰撞-(附带图解)浏览:3711 |
IP判断 (C语言代码)浏览:495 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:629 |