深搜练习2

2019-11-18

3095: 玉树搜救行动

时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte 总提交: 1990 测试通过:983

描述

自从玉树受灾以来，有关部门一直在现场抢救落难的人。他们用个种方法搜救，用上了搜救犬，有了搜救犬找到生命迹象就容易了。假设现场用一个矩阵表示，抢救的有多条搜救犬，受灾的人也有多个可能。例子:

#p.d#p#

#####.#

d……..#

######p

d表示搜救狗，p表示受灾的人，点表示可以通行的路，#表示石头挡住的路，不能通行。

搜救狗只能上下左右走，不能越过障碍物。

上面的那个例子最多可以救到2个人。因为第三个人被四周包围搜救狗无法到达。

输入

输入数据有多组。每组两个整数R，C, 2=<R,C<=100， R表示矩阵的行数，C表示矩阵的列数，然后输入相应矩阵，矩阵保证有搜救狗和受灾的人。当输入R=0且C=0时候输入结束。

输出

输出搜救狗最多能救多少受灾的人的数量。

样例输入

4 7

#p.d#p#

#####.#

d…..#

######p

0 0

样例输出

思路： 图上记下’d’,’p’的坐标，对’d’进行深搜，走过的为不能走，找到一个人++，直到深搜结束。对每一个’d’都深搜，最后输出总救出人数。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int n,m,c,a1,a2,f,s;
char gra[105][105];
bool vis[105][105];
int dx[10005],dy[10005],px[10005],py[10005];
int x[]={1,-1,0,0};
int y[]={0,0,1,-1};
void dfs(int xx,int yy){
    for(int i=0;i<a2;i++)
    {
        if(xx==px[i] && yy==py[i] )   //如果找到++
        {
            f++;
        }
    }

    for(int i=0;i<4;i++)
    {
        int sx=xx+x[i];
        int sy=yy+y[i];
        if(sx<n && sx>=0 && sy<m && sy>=0
           && !vis[sx][sy]&& gra[sx][sy]!='#')  //在图内且能走
        {
            vis[sx][sy]=1;          //图上修改为不能走
            ///printf("%d %d\n",dx,dy);
            dfs(sx,sy);            //递归
        }
    }
}
void init()   //初始化
{
    memset(vis,0,sizeof(vis));
    memset(dx,0,sizeof(dx));
    memset(dy,0,sizeof(dy));
    memset(px,0,sizeof(px));
    memset(py,0,sizeof(py));
}
int main()
{
    while(scanf("%d%d",&n,&m),n || m)
    {
        a1=0,a2=0;s=0;
        init();
        for(int i=0;i<n;i++)
        {
            getchar();
            for(int j=0;j<m;j++)
            {
                gra[i][j]=getchar();
                if(gra[i][j]=='d')
                {
                    dx[a1]=i;
                    dy[a1++]=j;
                }
                else if(gra[i][j]=='p')
                {
                    px[a2]=i;
                    py[a2++]=j;
                }
            }
        }
        for(int i=0;i<a1;i++)   //遍历'd'坐标
        {
            f=0;
            dfs(dx[i],dy[i]);
            s+=f;
        }
        printf("%d\n",s);
    }
    return 0;
}