一、解數(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; // 記錄被用過(guò)了
}
}
}
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)記用過(guò)了
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)記沒(méi)用
}
}
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)被訪問(wèn)過(guò)了
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; // 沒(méi)有訪問(wèn)到
}
// 定義一個(gè)上下左右移動(dòng)的向量
int dx[4] = {0, 0, -1, 1}; // x x x-1 x+1
int dy[4] = {1, -1, 0, 0}; // y+1 y-1 y y
bool 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ù)組未被訪問(wèn)過(guò)，當(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; // 先定義到訪問(wèn)過(guò)
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)記是否訪問(wèn)過(guò)
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)記一下訪問(wèn)過(guò)了
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; // 向量x
int y = dy[k] + j; // 向量y
if(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鏈接
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-835612.html
2、代碼
class Solution
{
public:
// 全局變量
int m, n;
bool visit[21][21]; // 用來(lái)記錄位置是否被訪問(wèn)過(guò)
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int ret; // 統(tǒng)計(jì)總路數(shù)
int step; // 記錄總共有幾個(gè)0
int 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) // 找到開(kāi)頭
{
x = i;
y = j;
}
}
}
step += 2; // 包含上首尾
visit[x][y] = true; // 標(biāo)記一下當(dāng)前位置被使用過(guò)
dfs(grid, x, y, 1); // 從第一層開(kāi)始往后遞歸
return ret;
}
void dfs(vector<vector<int>>& grid, int i, int j, int count/*用來(lái)記錄每一條路線的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、解析
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-835612.html
到了這里，關(guān)于【leetcode】深搜、暴搜、回溯、剪枝（C++）3的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
