DFS(深度优先搜索)

选定一个出发点后进行遍历，能前进则前进，若不能前进，回退一步再前进，或再回退一步后继续前进。依此重复，直到所有与选定点相通的所有顶点都被遍历。

参考资料：DFS原理白话解析

求全排列

3
123
132 
213 
231 
312 
321

#include<bits/stdc++.h>
using namespace std;
int n;
int num[110];
int vis[110];   

void dfs(int t){

    if(t==n+1){
        for(int i=1;i<=n;i++)
            cout<<num[i]<<" ";
            cout<<endl;
        return ;//回到上一层调用函数的地方
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0){  //没有被用过
            vis[i]=1;
            num[t]=i; 
            dfs(t+1);
            vis[i]=0;
         }

}
}
int main(){
    memset(vis,0,sizeof(vis));//如果放在调用的函数里面不可以 
    cin>>n;                 // 每次调用都更新 
    dfs(1);
    return 0;
}
在dfs中输出一组序列 123
return返回到dfs(3+1)的位置，运行vis[3]=0,该循环结束跳出，回到上一次函数调用的地方；
回到dfs(2+1)的地方，vis[2]=0,继续循环i=3，此时num[2] = 3，继续调用dfs(3+1)
得到num[3]=2;

补充关于next_permutation 求全排列的解法

#include<bits/stdc++.h>
using namespace std;
int a[5];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=i;
    do{
        for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";
            cout<<endl;
    }while(next_permutation(a+1,a+n+1));

    return 0;
}

例题补充

Oil Deposits

 注意点：走过 @ 记得标记成 *
        getchar吞行(因为先读入数字后读入字符数组)
#include<bits/stdc++.h>
using namespace std;
int n,m;
int dir[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};//定义方向
char mp[110][110],vis[110][110];

void dfs(int x,int y){
    for(int i=0;i<8;i++){
        int sx = x+dir[i][0];
        int sy = y+dir[i][1];
        if(mp[sx][sy]=='@'&&sx>=0&&sx<n&&sy>=0&&sy<m){
            mp[sx][sy]='*';
            dfs(sx,sy);
        }
    }
}
int main(){
    while(scanf("%d %d",&n,&m)&&n!=0&&m!=0){
        getcahr();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                cin >> mp[i][j];
        }
        int cnt =0 ;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(mp[i][j]=='@'){
                    dfs(i,j);
                    cnt++;
                }
            }
        }
        cout<<cnt<<endl;
    }
}

病毒溯源 dfs+邻接表

思路：其实就是找树中从根节点到叶节点的最长路径长度，并输出，明显的dfs，从
      根节点开始，求每个子节点的最长路径取max，并修改路径即可
      路径只需要用一个数组son【】保存即可
      如果有相同长度的路径，要按照字典序从小到大(vector排序)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10010, M = 10010;
int n;
int a[N][N];
vector<int>v[N];
vector<int>ans, temp;
int son[N];
bool st[N];

int dfs(int u) {
    int maxlen = 0;
    son[u] = -1;
    for (int i = 0; i < v[u].size(); i++) {
        //遍历u的每个孩子
        int len = dfs(v[u][i]);
        if (len > maxlen) {
            maxlen = len;
            son[u] = v[u][i];
        }
    }
    return maxlen + 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int cnt;
        scanf("%d", &cnt);
        while (cnt--) {
            int x;
            scanf("%d", &x);
            st[x] = true;
            v[i].push_back(x);
        }
        //按照字典序，升序排序，保证长度相同时，输出字典序小的那一个
        sort(v[i].begin(), v[i].end());
    }
    //找根节点
    int root = 0;
    while (st[root]) root++;
    printf("%d\n", dfs(root));
    printf("%d", root);
    while (son[root] != -1) {
        root = son[root];
        printf(" %d", root);
    }
    return 0;
}

手机的诱惑

#include<bits/stdc++.h>

using namespace std;
char Map[9][9];
int n,m,t,di,dj;
bool escape;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
void dfs(int si,int sj,int cnt)
{
    int i,temp;
    if(si>n||sj>m||si<=0||sj<=0)
        return;  
    if(cnt==t&&si==di&&sj==dj)
        escape=1;
    if(escape)
        return;
    temp=(t-cnt)-abs(si-di)-abs(sj-dj);
    if(temp<0||temp%2==1)
        return;
    for(i=0;i<4;i++)
 {
     if(Map[si+dir[i][0]][sj+dir[i][1]]!='X')
  {
     Map[si+dir[i][0]][sj+dir[i][1]]='X';
     dfs(si+dir[i][0],sj+dir[i][1],cnt+1);
     Map[si+dir[i][0]][sj+dir[i][1]]='.';    
  }    
 }    
}
int main()
{
     int i,j,si,sj;
     while(cin>>n>>m>>t)
 {
      if(n==0&&m==0&&t==0)
            break;
     int wall=0;
     for(i=1;i<=n;i++)
  {
    for(j=1;j<=m;j++)
   {
     cin>>Map[i][j];
     if(Map[i][j]=='S')
    {
         si=i;
         sj=j;    
    }
    else if(Map[i][j]=='D')
    {
        di=i;
         dj=j;    
    }
    else if(Map[i][j]=='X')
    wall++;    
   }    
  }
    if(n*m-wall<=t)
  {
     cout<<"NO"<<endl;
     continue;    
  }
    escape=0;
     Map[si][sj]='X';
     dfs(si,sj,0);
     if(escape)
     cout<<"YES"<<endl;
    else
     cout<<"NO"<<endl;    
 }
     return 0;    
}