【DFS练习】【最大的蛋糕块】-C++

超、凢脫俗 2021-11-01 07:28 261阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMzNjk1NA_size_16_color_FFFFFF_t_70]  
这道题目是一个基本的dfs模板(?)下面日常贴一波dfs的基本模板：

void dfs()//参数用来表示状态  
    {  
        if(到达终点状态)  
        {  
            ...//根据题意添加  
            return;  
        }  
        if(越界或者是不合法状态)  
            return;  
        if(特殊状态)//剪枝
            return ;
        for(扩展方式)  
        {  
            if(扩展方式所达到状态合法)  
            {  
                修改操作;//根据题意来添加  
                标记；  
                dfs（）；  
                (还原标记)；  
                //是否还原标记根据题意  
                //如果加上（还原标记）就是 回溯法  
            }  
        }  
    }

这道题的思路是：先输入，然后遍历一遍原图，如果遇到\#(蛋糕)就向四周扩散，同一块蛋糕全部变成’.’，然后cnt++，最后输出就可以了。直接改原图，不需要转换成01矩阵会简单一些。  
代码：

#include<bits/stdc++.h>
    using namespace std;
    int cnt=0;
    char a[1010][1010];
    int dir[4][2]={
        {1,0},{-1,0},{0,1},{0,-1}};
    bool visited[1010][1010];
    void dfs(int x,int y)
    {
    	visited[x][y]=1;
    	a[x][y]='.';
    	cnt++;
    	for(int i=0;i<4;i++)
    	{
    		int tx=x+dir[i][0];
    		int ty=y+dir[i][1];
    		if(a[tx][ty]=='#')
    		{
    			dfs(tx,ty);
    		}
    	}
    }
    int main()
    {
    	int n,m,ans=0;
    	cin>>n>>m;
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			cin>>a[i][j];
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			if(a[i][j]=='#')
    			{
    				cnt=0;
    				dfs(i,j);
    				ans=max(ans,cnt);
    			}
    		}
    	}
    	cout<<ans<<endl;
    }

转载于:https://www.cnblogs.com/moyujiang/p/11167741.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDMzNjk1NA_size_16_color_FFFFFF_t_70]: /images/20211101/c12b317df33546888d51cb43dc7e3038.png