Hrbust1143 泉水 DFS 水

z4zr 2013-05-31 PM 2152℃ 0条

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1143
题目大意
给出一个n*m的矩阵 和一个泉眼位置(p1,p2);
水会向和泉眼等高或者低的地方流
矩阵中每个数代表一个方格的高度
输出有水的方格数

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
3 4 1 5 1
2 3 3 4 7
4 1 4 1 1

Sample Output

6

大水啊。。。。。马虎的WA了*2
情何以堪

#include<stdio.h>
#include<string.h>
int mp[1005][1005];
int vis[1005][1005];
int n,m,p1,p2;
int ans;
int chk(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=m)return 1;
    else return 0;
}
void dfs(int x,int y){
    if(vis[x][y]==1)return;
    vis[x][y]=1;
    if(mp[x][y]<=mp[p1][p2]){
        ans++;
        if(chk(x-1,y))dfs(x-1,y);
        if(chk(x+1,y))dfs(x+1,y);
        if(chk(x,y-1))dfs(x,y-1);
        if(chk(x,y+1))dfs(x,y+1);
    }
    return;
}
int main(){
    while(scanf("%d%d%d%d",&n,&m,&p1,&p2)!=EOF){
        ans=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&mp[i][j]);
            }
        }
        dfs(p1,p2);
        printf("%d\n",ans);
    }
    return 0;
}
标签: dfs, hrbust, 递归, acm

非特殊说明,本博所有文章均为博主原创。

评论啦~