P1451 求细胞数量 题解

· · 题解

这是一道用DFS求联通块的题解

本人被坑了10余次

现奉上代码:


#include<bits/stdc++.h>//万能头
using namespace std;
int ma[105][105];//地图数组
int m,n,coun=0;
int dx[4]={0,0,1,-1};//四方向数组
int dy[4]={1,-1,0,0};//四方向数组
void dfs(int x,int y){//重点函数
    ma[x][y]=0;//标记为没有
    for(int i=0;i<4;i++){//记住是小于4而不是小于等于4啊
        x+=dx[i];y+=dy[i];//变换坐标
        if(x>0&&x<=n&&y>0&&y<=m&&ma[x][y]!=0)//如果不越界且大于0
        {
            dfs(x,y);、、继续搜索
        }
        x-=dx[i];y-=dy[i];//回溯一步
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
       for(int j=1;j<=m;j++)
       {
        scanf("%1d",&ma[i][j]);//每个变量只输入一位
       }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(ma[i][j]==0)//如果为0
            {
                continue;//返回
            }
            dfs(i,j); //搜索
            coun++;//计数
        }
    }
    cout<<coun;//输出
    return 0;
 } 

 这里还有两个普通的深搜模板
深度优先搜索算法框架1
int Search(int k)
　{
　for (i=1;i<=算符种数;i++)
　　if (满足条件)
　　   {
　　　　保存结果
　　　　if (到目的地) 输出解;
　　　           else Search(k+1);
　　　　恢复：保存结果之前的状态{回溯一步}
　 　  }
　}
 深度优先搜索算法框架2
int Search(int k)
　{
　  if  (到目的地) 输出解;
　　　else
　　　　for (i=1;i<=算符种数;i++)
　　　　　if  (满足条件) 
　　　　　　　{
　　　　　　　　保存结果;
　　　                  Search(k+1)
                             恢复：保存结果之前的状态{回溯一步}
　　　　　　　}
　}

做完这道题后，大家也可以做一下P1506 P1596 都是DFS求联通块的题目，用来提升自己的编程水平

最后，希望大家能学会DFS，也希望管理大大能通过此篇题解！