dfs总结

矫情吗；* 2022-05-29 12:49 165阅读 0赞

dfs解决全排列问题

典型题目：用数字 1~5进行全排列，显示出每一种情况并计算出总共有多少种情况。

#include <iostream>
    using namespace std;
    
    const int n = 5;
    int ans = 0;
    int a[n+1];
    int book[n] = {0};  //0 表示还没用 
    
    void bfs(int step) 
    {
    	if (step==n+1)  // **边界条件 
    	{
    		ans++;	//统计情况总数 
    		for (int j=1;j<=n;j++)  //显示每种可能 
    			cout<<a[j]<<" ";
    		cout<<endl;
    		return;  //  返回上一步 (这里的返回很重要) 
    	}
    	
    	for (int i=1;i<=n;i++)  //**遍历所有可能的数字 
    	{
    		if (book[i]==0)  //**判断情况是否已经处理过 
    		{  
    			a[step] = i;  //**尝试这个数字 
    			book[i] = 1;  //**把数字标记为【已尝试】 
    			bfs(step+1);  //**递归下一个位 
    			book[i] = 0;  //**尝试结束，取消标记 
    		}
    	}
    	
    	return;	 //返回 
    }
    
    int main()
    {
    	bfs(1);  //如果参数是 1，则边界条件为 n+1；如果是 0，边界则是 n 
    	 
    	cout<<ans<<endl;
    	return 0;
    }

dfs解决迷宫问题

题目：给出迷宫大小、迷宫简图、起点坐标，终点坐标。求到达终点的路径数和最短路径所需的步数。

#include <iostream>
    using namespace std;
    
    int maze[10][10];  
    int book[10][10] = {0};  // 标记该坐标是否走过 
    int dx[4] = {1,0,-1,0};  //方向 
    int dy[4] = {0,1,0,-1};
    
    int ans = 0;  //到达终点的路线数目 
    int minn = 99999;  // 最小步数 
    int m,n;  // 迷宫大小
    int sx,sy;  //起点 
    int gx,gy;  // 终点  
    
    void dfs(int x,int y,int step)
    {
    	if (x==gx && y==gy)  // **边界条件 
    	{
    		ans++; 
    		if (step < minn) minn = step;
    		return;  //返回上一步 (这里的返回很重要) 
    	}
    	
    	for (int k=0;k<4;k++)  // **遍历所有情况（枚举 4 个方向的走法 
    	{
    		int nx = x + dx[k];
    		int ny = y + dy[k];
    		
    		// **判断当前情况是否可用 
    		if (0<=nx && nx<m && 0<=ny && ny<n)  //判断是否有越界 
    		{
    			if (book[nx][ny] == 0 && maze[nx][ny] == 0)  // 判断是否已经走过或者是否是障碍
    			{
    				book[nx][ny] = 1;  //**标记这个点已经用过（走过） 
    				dfs(nx,ny,step+1); //**递归 
    				book[nx][ny] = 0;  //**尝试结束，取消这个点的标记 
    			} 
    		}
    	}
    	
    	return;
    }
    
    
    int main()
    {
    	int i,j;
    	cin>>m>>n;  // 迷宫的行，列 
    	cin>>sx>>sy>>gx>>gy;  //输入起点坐标和终点坐标 
    	for (i=0;i<m;i++)
    		for (j=0;j<n;j++)
    			cin>>maze[i][j];
    
    	book[0][0] = 1;  // （0，0）为起点，默认为已经走过		
    	
    	dfs(sx,sy,0);  //
    	
    	cout<<"路线数目: "<<ans<<endl;
    	cout<<"最短路径: "<<minn<<endl; 
    	
    	return 0;
    }

dfs大致的模版：

void dfs(int step)
    {
        if (...) 边界条件
        {
            ...
            return;   //返回上一步（这里一定要写）
        }
        
        for (i=0;i<n;i++)  尝试每一种可能
        {
            if (...)  判断当前可能是否可用
            {
                 ...
                 book[i] = 1;   //标记这个可能已经尝试
                 dfs(step+1);  //继续下一步
                 book[i] = 0;   //尝试结束，取消该点的标记（这里一定要写）
            }
        }
    
        return;
    }