dfs和回溯模版

dfs template

1
2
3
4
5
6
7
8
9
10
11
12
13

void f()  
{  
     if(符合边界条件)  
     {  

        ///////  
        return;  
     }  

     //某种形式的调用  
     f();  
}

回溯模版： 限制条件 if，选择 （for。。。）结束条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void DFS(int 当前状态)  
{  
      if(当前状态为边界状态)  
      {  
        记录或输出  
        return;  
      }  
      for(i=0;i<n;i++)       //横向遍历解答树所有子节点  
      {  
           //扩展出一个子状态。  
           修改了全局变量  
           if(子状态满足约束条件)  
            {  
              dfs(子状态)  
           }  
            恢复全局变量//回溯部分  
      }  
}

BFS和DFS相似。BFS显式用队列，DFS隐式用栈，即递归。
当然，对于DFS，用递归可能会造成栈溢出，所以也可以更改为显示栈。

经典例题： 走迷宫
*表示可走

#表示障碍
T表示出口
入口是(1,1)，数据保证左上角是入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
using namespace std;

char maze[100][100];
bool flag[100][100];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int m,n;

bool dfs(int x,int y)
{
    flag[x][y]=1;              //走过的路标记为1
    if(maze[x][y]=='T')return true;
    for(int i=0;i<4;i++)       //四个方向
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(flag[nx][ny]==0||maze[nx][ny]=='*'||maze[nx][ny]=='T'&&nx>0&&ny>0&&nx<m+1&&ny<n+1)
        {
            return dfs(nx,ny);   
            flag[nx][ny]=0;    //回溯，将标记重新标记为0
        }
    }
    return false;             //找不到返回false
}

int main()
{

    while(cin>>m>>n){
    memset(maze,0,sizeof(maze));
    memset(flag,0,sizeof(flag));
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>maze[i][j];
    if(dfs(1,1))cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    }
}

回溯的两种写法：

递归写法和迭代写法，链接：https://blog.csdn.net/man_sion/article/details/74993907