泉水
|
||||||
| Description | ||||||
| Leyni是一个地址调查员，有一天在他调查的地方突然出现个泉眼。由于当地的地势不均匀，有高有低，他觉得如果这个泉眼不断的向外溶出水来，这意味着这里在不久的将来将会一个小湖。水往低处流，凡是比泉眼地势低或者等于的地方都会被水淹没，地势高的地方水不会越过。而且又因为泉水比较弱，当所有地势低的地方被淹没后，水位将不会上涨，一直定在跟泉眼一样的水位上。 |
||||||
| Input | ||||||
| 有若干组数据，每组数据的第一行有四个整数n,m,p1,p2(0<n,m,p1,p2<=1000)，n和m表示当前地图的长和宽，p1和p2表示当前地图的泉眼位置，即第p1行第p2列，随后的n行中，每行有m个数据。表示这每一个对应坐标的高度。 |
||||||
| Output | ||||||
| 输出对应地图中会有多少个格子被水充满。 |
||||||
| Sample Input | ||||||
| 3 5 2 3 |
||||||
| Sample Output | ||||||
| 6 |
||||||
| Author | ||||||
| 孔繁阳 |
思路：本题是深搜的简单应用
1：建立vis数组记录访问情况，访问过的标记为1，未访问过的为0。
2：以泉眼为起点向四个方向进行搜索，搜索到下一个点时，便以这个点为中心，再向四个方向进行搜索。
3：如果某点已经访问过，则搜索到该点时，结束本次递归调用。
4,：某点进入调用函数的条件是：（1）坐标不越界（2）此点高度小于或等于泉眼
上代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;const int LL=1005;int n,m,p1,p2;///n和m表示当前地图的长和宽，p1和p2表示当前地图的泉眼位置
int sum;///计算满足的点数int Map[LL][LL];///输入用数组
int vis[LL][LL];///记录访问状态数组int X[4]={1,-1,0,0};///x y坐标一一对应，分别对应四个方向
int Y[4]={0,0,1,-1};void dfs(int x,int y)
{if(vis[x][y]){return ;///已访问过的话，直接结束调用}if(!vis[x][y]){sum++; ///未访问的话。表示此点满足条件。sum自增vis[x][y]=1;///标记为1，已访问}for(int i=0;i<4;i++)///分别访问四个方向{int x1=x+X[i];int y1=y+Y[i];if(x1<=n&&x1>=1&&y1<=m&&y1>=1&&Map[x1][y1]<=Map[p1][p2])///坐标不越界，且此点高度小于等于泉眼{dfs(x1,y1);///满足条件则进入调用}}
}int main()
{while(cin>>n>>m>>p1>>p2){
// memset(Map,0,sizeof(Map)); 这句清空语句一加上就会WA，原因不明。。。。memset(vis,0,sizeof(vis));///注意清空记录数组for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&Map[i][j]);}}sum=0;///初始化为零dfs(p1,p2);///从泉眼开始搜索printf("%d\n",sum);}return 0;
}
注意调用条件！！！！！！