本文主要是介绍HUBUST-1143 泉水，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题：
传送门
题意：
给一个地图，一个泉眼，求泉眼附近所有可以到达的高度不大于泉眼的点的个数(包括泉眼本身)
思路：
bfs直接搜索，这里注意，一定要在for循环内把vis[nx, ny]置为1，要不然可能会出现重复的情况(如果(i, j)比泉眼低，(i-1, j)和(i, j-1)也都比泉眼低， 那么在u=(i-1, j)时，cnt++了，在u=(i, j-1)时，也进行了cnt++)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>using namespace std;
const int MAX = 1002;int mp[MAX][MAX];
int dr[4][2]={-1,0,1,0,0,1,0,-1};
int vis[MAX][MAX];
int n, m, p1, p2;
int cnt = 0;
struct node {int x, y;
};
queue<node> q;void bfs() {node nd;nd.x=p1;nd.y=p2;vis[p1][p2]=1;q.push(nd);while (!q.empty()) {node u = q.front();q.pop();for (int i=0;i<4;i++) {int nx=u.x+dr[i][0], ny=u.y+dr[i][1];if ((nx>=1&&nx<=n) && (ny>=1&&ny<=m) && !vis[nx][ny] && mp[nx][ny] <= mp[p1][p2]) {nd.x=nx;nd.y=ny;q.push(nd);vis[nx][ny]=1;cnt++;}}}
}
void init() {cnt=0;while (!q.empty()) {q.pop();}for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)vis[i][j]=0;
}
int main()
{while (cin>>n>>m>>p1>>p2) {init();for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)cin>>mp[i][j];bfs();cout<<cnt+1<<endl;}return 0;
}
这篇关于HUBUST-1143 泉水的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
