---

一、解數(shù)獨(dú)

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 全局變量bool row[9][10]; // 行bool col[9][10]; // 列bool grid[3][3][10]; // 小格子void solveSudoku(vector<vector<char>>& board) {// 初始化for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] != '.') // 是數(shù)就填進(jìn)去{int num = board[i][j] - '0'; // 記錄一下數(shù)row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true; // 記錄被用過了}}}dfs(board);}bool dfs(vector<vector<char>>& board){for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){// 填數(shù)if(board[i][j] == '.'){for(int num = 1; num <= 9; num++) // 從1-9一個(gè)個(gè)遍歷填數(shù){if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]){board[i][j] = num + '0'; // 填入進(jìn)去row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true; // 標(biāo)記用過了if(dfs(board) == true) return true; // 表示可以填進(jìn)去// 恢復(fù)現(xiàn)場(chǎng)board[i][j] = '.';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false; // 標(biāo)記沒用}}return false; // 1-9都不行}}}return true; // 走完了，填完了，返回true}
};

3、解析

二、單詞搜索

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 全局變量bool visit[7][7];int m, n;bool exist(vector<vector<char>>& board, string word) {m = board.size(); // 總共有多少行n = board[0].size(); // 一行有多少個(gè)for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){// 匹配if(word[0] == board[i][j]){visit[i][j] = true; // 標(biāo)記該點(diǎn)已經(jīng)被訪問過了if(dfs(board, i, j, word, 1/*從第一個(gè)位置往下走*/)) return true; // 遞歸到下一層visit[i][j] = false; // 第一個(gè)點(diǎn)位置錯(cuò)誤，找下一個(gè)第一個(gè)對(duì)應(yīng)的點(diǎn)}}}return false; // 沒有訪問到}// 定義一個(gè)上下左右移動(dòng)的向量int dx[4] = {0, 0, -1, 1}; // x x x-1 x+1int dy[4] = {1, -1, 0, 0}; // y+1 y-1 y ybool dfs(vector<vector<char>>& board, int i, int j, string word, int pos){// 遞歸出口if(pos == word.size()){return true;}for(int k = 0; k < 4; k++){int x = dx[k] + i; // x坐標(biāo)int y = dy[k] + j; // y坐標(biāo)// 不越界，當(dāng)前visit數(shù)組未被訪問過，當(dāng)前字符和word相對(duì)應(yīng)字符相同if(x >= 0 && x < m && y >=0 && y < n && visit[x][y] == false && word[pos] == board[x][y]){visit[x][y] = true; // 先定義到訪問過if(dfs(board, x, y, word, pos + 1)) return true; // 遞歸下一層visit[x][y] = false; // 恢復(fù)現(xiàn)場(chǎng)}}return false;}
};

3、解析

三、黃金礦工

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 全局變量bool visit[16][16]; // 標(biāo)記是否訪問過int m, n; // m是行，n是列int sum; // 總和int path; // 每次走的路徑int getMaximumGold(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] != 0) // 先找到第一個(gè)非零元素{visit[i][j] = true; // 標(biāo)記一下訪問過了path += grid[i][j]; // 路徑加上dfs(grid, i, j, path); // 遞歸visit[i][j] = false; // 找下一個(gè)非零元素path -= grid[i][j];} }}return sum;}int dx[4] = {0, 0, 1, -1}; // 上下左右int dy[4] = {1, -1, 0, 0}; // 上下左右void dfs(vector<vector<int>>& grid, int i, int j, int path){// 遞歸出口sum = max(sum, path); // 這里直接用算法max找最大值for(int k = 0; k < 4; k++){int x = dx[k] + i; // 向量xint y = dy[k] + j; // 向量yif(x >= 0 && x < m && y >= 0 && y < n && visit[x][y] == false && grid[x][y] != 0){visit[x][y] = true;path = path + grid[x][y]; // 路徑加上dfs(grid, x, y, path);visit[x][y] = false; // 恢復(fù)現(xiàn)場(chǎng)path = path - grid[x][y];}}}
};

3、解析

四、不同路徑III

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 全局變量int m, n;bool visit[21][21]; // 用來記錄位置是否被訪問過int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int ret; // 統(tǒng)計(jì)總路數(shù)int step; // 記錄總共有幾個(gè)0int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size(); // 行n = grid[0].size(); // 列int x = 0; // 記錄1的橫坐標(biāo)int y = 0; // 記錄1的縱坐標(biāo)for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(grid[i][j] == 0){step++; // 統(tǒng)計(jì)有幾個(gè)0}else if(grid[i][j] == 1) // 找到開頭{x = i;y = j;}}}step += 2; // 包含上首尾visit[x][y] = true; // 標(biāo)記一下當(dāng)前位置被使用過dfs(grid, x, y, 1); // 從第一層開始往后遞歸return ret;}void dfs(vector<vector<int>>& grid, int i, int j, int count/*用來記錄每一條路線的0的個(gè)數(shù)*/){// 遞歸出口if(grid[i][j] == 2){if(count == step){ret++;}return;}for(int k = 0; k < 4; k++){int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && grid[x][y] != -1){visit[x][y] = true;dfs(grid, x, y, count + 1);visit[x][y] = false;}}}
};

3、解析