DFS

一、 背包，资源分配等求一维线性最值或全排列问题

void dfs(int x,int sum){
    if(x>n)return;  //当前数量超过背包容量，资源总数，或数字总数，return
    else{       
        if(sum>maxP)maxP=sum;
        for(int i=0;i<8;i++)//遍历一维数组
            if(vis[i]==0){//遍历没有被访问过的节点
                vis[i]=1;
                dfs(x+w[i],sum+pian[i]);
                vis[i]=0;//回溯
            }
    }
}

另一种写法

void dfs2(int index,int sumC,int sumW){
    if(index==8){

        return;
    }
        dfs2(index+1,sumC,sumW);//跳过index
    if(sumW <= n) {
        if (  sumC > maxP)
            maxP = sumC;
        dfs2(index + 1, sumC + pian[index], sumW + w[index]);//包含index
    }
}

二、地图问题

回溯标记是否需要还原

​ 如果问题是求，所有可能的情况，如所有的可能路径，所有的排列，则需要需要还原。此时 123和132被认为是两条路

​ 如果问题是求面积，求最佳路径，则不需要

添加dir数组，进行移动

岛屿的最大面积

void dfs(int ax,int ay,vector<vector<int>>& grid){
        w++;
        for(int k=0;k<4;k++){
            int x=ax+dir[k][0];
            int y=ay+dir[k][1];
            if(checkV(x,y,grid)){
                visited[x][y]=1;
                dfs(x,y,grid);
            }
        }
    }

第二种递归解法

 int maxAreaOfIsland(int grid[][]) {
        int max = 0; // 记录最大岛屿面积
       
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) { // 
                    int count = DFS(grid, visited, i, j, 0);
                    max = max > count ? max : count;
                }
            }
        }
        return max;
    }

  int DFS(int grid[][],bool visited[][],int x,int y,int count) {
        if (!valid(grid, visited, x, y)) {
            return count;
        }
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) { // 上下左右进行遍历
            count = DFS(grid, visited, x + move[i][0], y + move[i][1], count);
        }
        return count+1; // 更新岛屿面积
    }

解数独

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示

// row[x][u]表示第x行是否已经填过数字u（0-8）
    // col[y][u]表示第y行是否已经填过数字u（0-8）
    // box[x / 3][y / 3][u]表示第[x/3,y/3]个box是否已经填过数字u（0-8）

    bool row[9][9] = {0}, col[9][9] = {0}, cell[3][3][9] = {0};
    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i ++ ) {
            for (int j = 0; j < 9; j ++ ) {
                char c = board[i][j];
                if (c != '.') {
                    int u = c - '1'; // u: '1' - '1' = 0
                    row[i][u] = col[j][u] = cell[i / 3][j / 3][u] = true;
                }
            }
        }

        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>>& board, int x, int y) {
        if (y == 9) x ++ , y = 0; // 先改变
        if (x == 9) return true; // 填完所有格子，返回true

        if (board[x][y] != '.') return dfs(board, x, y + 1);
        
        for (int i = 0; i < 9; i ++ ) {
            if (!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
                board[x][y] = i + '1';
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;

                // 如果下面搜索后是对的，就提前返回，不恢复现场(因为要修改board);
                // 如果是false就恢复现场（这个方法很巧妙）
                if (dfs(board, x, y + 1)) return true; 
                board[x][y] = '.';
                row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = 0;

            }
        }
        return false;
    }