dfs入门题目

矫情吗；* 2024-03-26 15:01 53阅读 0赞

> **题目链接：**  
> [P1451 求细胞数量][P1451]  
> **题目描述：**  
> ![在这里插入图片描述][d63e62cd42fa43daa791d6d5a2ce4378.png]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    
    using namespace std;
    
    int n,m;
    char mp[110][110];//存储地图
    int ans=0;//记录细胞数量
    
    void dfs(int x,int y)
    {
        
        if(x<1||y<1||x>n||y>m||mp[x][y]=='0') return;//退出搜索的条件
        
        else
        {
        
            mp[x][y]='0';
                dfs(x,y-1);
            dfs(x-1,y); dfs(x+1,y);//四个方向进行搜索 上，右，下，左。
                dfs(x,y+1);
        }
    }
    
    int main()
    {
        
        cin>>n>>m;
        
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>mp[i][j];//输入地图
        
        
        for(int i=1;i<=n;++i)
        {
        
            for(int j=1;j<=m;++j)
            {
        
                if(mp[i][j]!='0')//如果遇到细胞则进行搜索
                {
        
                    ans++;
                    dfs(i,j);//从这个坐标开始搜索 且 拓展
                }
            }
        }
        cout<<ans<<endl;
        
        return 0;
    }

> **题目链接：**  
> [Counting Sheep数羊 ][Counting Sheep_]  
> **题目描述：**  
> ![在这里插入图片描述][6c4b39eaacf84a108d360b1b4ff3e55b.png]

#include<stdio.h>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    using namespace std;
    
    int n,m;
    char arr[110][110];
    void dfs(int x,int y)
    {
        
    	if(x<1||y<1||x>n||y>m||arr[x][y]=='.')
    		return;
    	else
    	{
        
    		arr[x][y]='.';
    			dfs(x,y-1);
    	dfs(x-1,y);		dfs(x+1,y);
    			dfs(x,y+1);
    	}
    	
    }
    
    int main()
    {
        
    	int t;
    
    	cin>>t;
    	while(t--)
    	{
        
    		int ans=0;
    		m=0;n=0;
    		memset(arr,0,sizeof(arr));
    		cin>>n>>m;
    		for(int i=1;i<=n;++i)
    			for(int j=1;j<=m;++j)
    				cin>>arr[i][j];
    		
    		for(int i=1;i<=n;++i)
    		{
        
    			for(int j=1;j<=m;j++)
    			{
        
    				if(arr[i][j]=='#')
    				{
        
    					ans++;
    					dfs(i,j);
    				}
    			}
    		}
    		cout<<ans<<endl;
    	}
    	return 0;
    }

**这个题目和上一个题目很类似，基本就是一个类型的题目，所以划归为一道基础的dfs算法题目**

小tips：我在学习算法的时候会遇到很多难受的地方，比如学了然后还是会遇到题目不会写，其实跟我一个学长说的差不多，`我目前的问题`其实就是`刷的题目不够多`，以至于，我目前`掌握不了这个算法`。所以现在自己还是需要`多写刷题目`，`多打一些比赛`去`提升自己`。

[P1451]: https://www.luogu.com.cn/problem/P1451
[d63e62cd42fa43daa791d6d5a2ce4378.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ab0ee6d0a85b499ba02de5e6e54c0cd3.png
[Counting Sheep_]: https://acm.hdu.edu.cn/showproblem.php?pid=2952
[6c4b39eaacf84a108d360b1b4ff3e55b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4d9398b6487e44aeb51dbd2dd42c94c0.png