P1596 [USACO10OCT]Lake Counting S

一篇比较水的题,我还是卡了好久,
其实一开始我用了stl队列写出来了,为了挑战一下自己,就决定分别用DFS,BFS(手写队列),BFS(queue)三种方法写了出来
## DFS代码如下

\#include<iostream>
\#include<cstdio>
\#include<math.h>
\#include<algorithm>
\#include<cstring>//常规五行起步 
using namespace std;
char mapp[200][200];//建图(题目中是W与.用的是char数组) 
int m,n,ans=0;
void dfs(int x,int y){//基本的dfs代码 
 mapp[x][y]='.';//先把该点置为.防止下次再搜到 
 int dx,dy;
 for(int i=-1;i<=1;i++){
 for(int j=-1;j<=1;j++){//一开始想写8联通的,后来一直出的是120,就放弃了,改用的循环嵌套。 
 dx=x+i;
 dy=y+j;
 if(dx>=0&&dx<=n&&dy>=0&&dy<m&&mapp[dx][dy]=='W'){//判断是否在图里 
 dfs(dx,dy);//回溯 
 }
 }
 }
 return;
} 
int main()
{ cin>>n>>m;
 for(int i=0;i<n;i++)
 for(int j=0;j<m;j++)
 cin>>mapp[i][j]; //输入地图 
 for(int i=0;i<n;i++)
 for(int j=0;j<m;j++)
 if(mapp[i][j]=='W')//如果有水,就进行判断,搜索。 
 {
 //cout<<i<<" "<<j<<endl;
 dfs(i,j);
 ans++;//水洼数+ 1 
 }
 cout<<ans;//输出结果 
 return 0;
}

#### 上面就是dfs
然后bfs的主要部分是队列的判断,考虑队列中的头指针与尾指针

 ans++;//每次搜索+1 
 int head=0,tail=1,x,y,ans=0;//head是头,tail是尾 
 mapp[p][q]='.';//当前点置为已查 
 while(head<tail)//队列清空则此水洼搜索完成 
 {
 head++;//头+1 
 a[1][1]=p;//18 19行把当前点存入队列 
 a[1][2]=q; 
 for(int i=1;i<=8;i++)//8联通搜索的基本 
 {
 x=a[head][1]+dx[i];
 y=a[head][2]+dy[i]; 
 if(x>=0&&x<=n&&y>=0&&y<=m&&mapp[x][y]=='W'){//在图内判断 
 tail++;//尾++ 
 a[tail][1]=x;
 a[tail][2]=y;
 //cout<<" "<<x<<" "<<y<<endl;
 mapp[x][y]='.'; //当前点赋0
 } 
 }
 }

## 上面的是对于bfs的代码
## 这是手写的队列。
## 然后ac的全体代码在下面-
(用手写队列的话,这个题是有坑的,好像是第4个还是第几个点,它的输入数据是全部为W,所以
# 队列一定要开大)

\#include<iostream>
\#include<cstdio>
\#include<math.h>
\#include<algorithm>
\#include<cstring>//常规5行 
using namespace std;
char mapp[200][200];
int dx[9]={0,0,0,1,1,1,-1,-1,-1},dy[9]={0,1,-1,0,1,-1,0,1,-1};//八连的判断 
int a[10001][3];//队列 
int n,m,ans;
int bfs(int p,int q) 
{ ans++;//每次搜索+1 
 int head=0,tail=1,x,y,ans=0;//head是头,tail是尾 
 mapp[p][q]='.';//当前点置为已查 
 while(head<tail)//队列清空则此水洼搜索完成 
 {
 head++;//头+1 
 a[1][1]=p;//18 19行把当前点存入队列 
 a[1][2]=q; 
 for(int i=1;i<=8;i++)//8联通搜索的基本 
 {
 x=a[head][1]+dx[i];
 y=a[head][2]+dy[i]; 
 if(x>=0&&x<=n&&y>=0&&y<=m&&mapp[x][y]=='W'){//在图内判断 
 tail++;//尾++ 
 a[tail][1]=x;
 a[tail][2]=y;
 //cout<<" "<<x<<" "<<y<<endl;
 mapp[x][y]='.'; //当前点赋0
 } 
 }
 }
}
int main()

{ cin>>n>>m;
 for(int i=0;i<n;i++)
 for(int j=0;j<m;j++)
 cin>>mapp[i][j]; //建图 
 for(int i=0;i<n;i++)
 for(int j=0;j<m;j++)
 if(mapp[i][j]=='W')//判断 
 {
 //cout<<i<<" "<<j<<endl;
 bfs(i,j);//搜索开始 
 }
 cout<<ans;
 return 0;
}

## 最后就是我利用queue写的代码了,这个代码是我当初在GXL大佬的帮助下写出来的,
# 所以(感谢GXL大佬的教的广搜以及STL队列)

\#include<iostream>
\#include<queue>
using namespace std;
char dd[115][115];
int mapp[115][115];
int go[9][2]{{0,0},{1,1},{1,0},{1,-1},{0,1},{0,-1},{-1,1},{-1,0},{-1,-1}};
struct STU{
 int xx;
 int yy;
};
int m,n,qx,qy,tx,ty,ans;
queue<STU>q;
void bfs(int x,int y)
{
 q.push((STU){x,y});
 mapp[x][y]=0;
 while(q.size()!=0)
 {
 qx=q.front().xx;
 qy=q.front().yy;
 q.pop();
 for(int i=1;i<=8;i++)
 {
 tx=qx+go[i][0];
 ty=qy+go[i][1];
 if(tx<1||tx>n||ty<1||ty>m)
 {
 continue;
 }
 if(mapp[tx][ty]==0)
 {
 continue;
 }
 mapp[tx][ty]=0;
 q.push((STU){tx,ty});
 }
 }
}
int main()
{
 cin>>n>>m;
 for(int i=1;i<=n;i++)
 {
 for(int j=1;j<=m;j++)
 {
 cin>>dd[i][j];
 if(dd[i][j]=='W')
 {
 mapp[i][j]=1;
 }
 }
 }
 for(int i=1;i<=n;i++)
 {
 for(int j=1;j<=m;j++)
 {
 if(mapp[i][j]==1)
 {
 ans++;
 bfs(i,j);
 }
 }
 }
 cout<<ans;
 return 0;
}

最后一个代码没写什么注释,凑合着看看吧,
这个题还是比较水的,所以我也没具体说明这个题的思路和解题过程(其实就是数水洼,以这个点为中心的九宫格内的水可与其构成一个水洼,计算最终水洼的数量)
这个题大体就是这样,看在我辛苦码字的份上,就留个赞再走吧

博客发在洛谷上了,这是复制的,可以看洛谷上的

<https://www.luogu.com.cn/blog/840-114/p1596-usaco10octlake-counting-s&gt;

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。