水流问题

水流问题(bfs)

样例输入：

5 5
1 2 2 3 5
3 2 3 4 4
2 4 5 3 1
6 7 1 4 5
5 1 1 2 4

输出：

7

这道题目也不是很难，bfs搜两次就好了，一次太平洋，一次大西洋，然后遍历标记数组，都能到的就累加。搓了很久没做出来又是很基本的错误，忘了初始化标记数组。。。还是不够仔细。

#include
using namespace std;
int maze[155][155],a[155][155],b[155][155],vis[155][155];
int n,m,ans;
int to[4][2]={1,0,-1,0,0,1,0,-1};
inline bool check(int x,int y){if(x>=0&&x<n&&y>=0&&y<m&&vis[x][y]==0)return true;return false;
}
struct node{int x,y,h;
}now;
inline void bfs(){queue<node>q;memset(vis,0,sizeof(vis));if(ans==1){//ans为1时把太平洋的点全部推入队列for(int i=0;i<n;i++){q.push(node{i,0,maze[i][0]});vis[i][0]=1;}for(int i=0;i<m;i++){q.push(node{0,i,maze[0][i]});vis[0][i]=1;}}else{//不然为大西洋for(int i=0;i<n;i++){q.push(node{i,m-1,maze[i][m-1]});vis[i][m-1]=1;}for(int i=0;i<m;i++){q.push(node{n-1,i,maze[n-1][i]});vis[n-1][i]=1;}}while(!q.empty()){//基本bfs操作now=q.front();q.pop();if(ans==1){a[now.x][now.y]=1;}else{b[now.x][now.y]=1;}for(int i=0;i<4;i++){int xx=now.x+to[i][0];int yy=now.y+to[i][1];if(check(xx,yy)&&now.h<=maze[xx][yy]){vis[xx][yy]=1;q.push(node{xx,yy,maze[xx][yy]});}}}
}
int main(){while(scanf("%d %d",&n,&m)!=EOF){for(int i=0;i<n;i++){for(int j=0;j<m;j++){scanf("%d",&maze[i][j]);}}memset(a,0,sizeof(a));//标记一定要清空，一直错在没初始化memset(b,0,sizeof(b));ans=1;bfs();ans=2;bfs();int sum=0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(a[i][j]>0&&b[i][j]>0){sum++;}}}printf("%d\n",sum);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！