Train-2

ans;                              //答案，常常用全局变量表示
void dfs(层数，其他参数){
    if (到达目的地、或者出局){    //到达最底层，或者满足条件退出 
        更新答案ans;              //答案一般用全局变量表示，ans是最优解
        return;                   //递归返回，即返回到上一层
    }
    (剪枝)                        //在进一步DFS之前剪枝
    for (用i遍历下一层所有可能的情况)    //对每一个情况继续DFS 
        if (used[i] == 0) {        //如果状态i没有处理过，就可以进入下一层dfs
            used[i] = 1;           //标记状态i为已经使用，在后续dfs时不能再使用
            dfs(层数+1，其他参数);      //下一层，即搜小规模后继续dfs
            used[i] = 0;           //恢复状态i，回溯时，不影响上一层对这个状态的使用
        }
    return;                        //返回到上一层
}

全排列

#include<bits/stdc++.h>
using namespace std;x
int n;
int vis[10];    // 访问标记
int a[10];      //需要做全排列的数组
int b[10];      //当前DFS得到的全排列
void dfs(int step) {
    if (step == n+1) {     //已经对n个数做了全排列，输出全排列
        for (int i=1; i<=n; i++)
            printf("%5d",b[i]);
        printf("\n");
        return;            //结束，不再继续DFS
    }
    for (int i = 1; i <= n; i++) {    //遍历每个a[i]，放进全排列中
        if (vis[i] == 0) {   // 数字a[i]不在前面得到的排列中
            b[step] = a[i];  // 把a[i]放进排列
            vis[i] = 1;      // 保存现场：a[i]不能在后面继续用
            dfs(step+1);     // 继续把后面的数放进排列
            vis[i] = 0;      // 恢复现场：a[i]重新可以使用
        }
    }
    return;
}
int main() {
    cin >> n;
    for (int i=1; i<=n; i++)  a[i]=i;   //赋值得到n个数
    dfs(1);  //对a[1]~a[n]做全排列
    return 0;
}

最大连通

#include<bits/stdc++.h>
using namespace std;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};  //四个方向
char g[100][100];
int n = 30, m = 60;
int dfs(int x, int y){      //当前位于坐标[x,y]
    if (g[x][y] == '0')   return 0;
    g[x][y] = '0';         //把这个点从1改为0，后面不再搜它
    int ans = 1;           //统计这个连通块的大小
    for (int i = 0; i < 4; i++ ) {           //遍历它的4个邻接
        int nx = x + dx[i], ny = y + dy[i];   //一个邻居的坐标
        if (nx<0 || ny<0 || nx>=n || ny>=m)   continue;    //这个邻居是否在边界内
        ans += dfs(nx, ny);
    }
    return ans;
}
int main(){
    for (int i = 0; i < n; i++ )  cin >> g[i];
    int ans = 0;
    for (int i = 0; i < n; i++ )
        for (int j = 0; j < m; j++ )
            if (g[i][j] == '1')
                ans = max(ans, dfs(i, j));
    cout << ans;
    return 0;
}

全球变暖

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char mp[N][N];                //地图
int vis[N][N]={0};            //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag;                     //用于标记这个岛中是否被完全淹没
void dfs(int x, int y){
    vis[x][y] = 1;            //标记这个'#'被搜过。注意为什么放在这里
    if( mp[x][y+1]=='#' && mp[x][y-1]=='#' &&
        mp[x+1][y]=='#' && mp[x-1][y]=='#'   )
        flag = 1;             //上下左右都是陆地，这是一个高地，不会淹没
    for(int i = 0; i < 4; i++){     //继续DFS周围的陆地
        int nx = x + d[i][0], ny = y + d[i][1];
        if(vis[nx][ny]==0 && mp[nx][ny]=='#')    //注意为什么要判断vis[][]                
            dfs(nx,ny);             //继续DFS未搜过的陆地，目的是标记它们
    }
}
int main(){
    int n;   cin >> n;
    for (int i = 0; i < n; i++)   cin >> mp[i];
    int ans = 0 ;
    for(int i = 0; i < n; i++)    //DFS所有像素点
        for(int j = 0; j < n; j++)
            if(mp[i][j]=='#' && vis[i][j]==0){
                flag = 0;         //假设这个岛被淹
                dfs(i,j);         //找这个岛中有没有高地，如果有,置flag=1
                if(flag == 0) ans++;   //这个岛确实被淹了，统计被淹没岛的数量    
            }
    cout<<ans<<endl;
    return 0;
}
Table Of Contents
Train-2
全排列
最大连通
全球变暖