N皇后
题解
1. 画出决策树
2. 全局变量：ret用来统计结果，path统计每次的路径，checkcol检查行有没有Q，checkdig1检查主对角线有没有Q，checkdig2检查副对角线有没有Q
3. 剪枝：使用哈希表的策略，每一行不需要检查，每次都递归每一行该放的不会出现攻击，主对角线斜率一样，利用y-x = b，每一条线上截距是相同的，如果出现相同的就表明放过了Q，y-x可能为负数所以加上了n，副对角线y + x = b，和主对角线类似
4. 回溯：将列，主对角线和副对角线变为false，path[row][col]恢复为点
5. 递归出口：行越界的时候填完矩阵
代码
class Solution
{
public:
// 检查列,主对角线和副对角线
// 行每次都只放一个不用检查,不会出现攻击
bool checkcol[10],checkdig1[20],checkdig2[20];
vector<vector<string>> ret;
vector<string> path;
int n;
vector<vector<string>> solveNQueens(int _n)
{
n = _n;
path.resize(n);
for(int i = 0;i < n;i++)
{
path[i].append(n,'.');
}
dfs(0);
return ret;
}
void dfs(int row)
{
if(n == row)
{
ret.push_back(path);
return;
}
for(int col = 0;col < n;col++)// 放置每一行
{
if(!checkcol[col] && !checkdig1[row + col] && !checkdig2[col-row+n])
{
path[row][col] = 'Q';
checkcol[col] = checkdig1[row + col] = checkdig2[col-row+n] = true;
dfs(row+1);
// 恢复现场
checkcol[col] = checkdig1[row + col] = checkdig2[col-row+n] = false;
path[row][col] = '.';
}
}
}
};
有效的数独
题解
1. 算法原理：去遍历这个数独，如果遇到了数字就判断这个数字是否在这一行，这一列，这一个方格中，如果不在就标记为true，如果在就直接返回false，说明出现了第二次了
2. bool checkrow[i][nums]：用来检查这一行是否存在nums这个数
bool checkcol[j][nums]：用来检查这一列是否存在nums这个数
bool check[i/3][j/3][nums]：用来检查小方格中是否存在nums这个数，除3是把9 * 9的矩阵分为0，1，2下标的3*3的小方格，刚好第一个小方格中0，1，2下标的数除3都是0，第二，三个小方格也是如此
代码
class Solution
{
public:
bool checkrow[9][10];// 检查行
bool checkcol[9][10];// 检查列
bool check[3][3][10];// 检查小方格
bool isValidSudoku(vector<vector<char>>& board)
{
for(int row = 0;row < 9;row++)
{
for(int col = 0;col < 9;col++)
{
if(board[row][col] != '.')
{
int nums = board[row][col] - '0';
if(checkrow[row][nums] || checkcol[col][nums] || check[row/3][col/3][nums])
return false;
checkrow[row][nums] = checkcol[col][nums] = check[row/3][col/3][nums] = true;
}
}
}
return true;
}
};
独解数
题解
1. 画出决策树
2. 全局变量：checkcol检查列是否存在相同的数，checkrow检查行是否存在相同的数，gird检查小方格是否存在相同的数
3. 剪枝：bool dfs(board)，如果这一行最终有一个格子填不了了，就返回false，不往后填了，返回到上一层去填正确的数
4. 回溯：填了的数bool变为false，然后board恢复为点
5. 递归出口：函数走完填完所有的格子就结束了
6. 算法原理：这题主要考察三个返回，第一个返回，如果填完了dfs返回true了，就不需要填下一个i了，第二个返回，如果所有数都不满足，说明前面填错了，返回上一层重新填，第三个返回，如果所有有点的格子都填完了，并且没有错，就返回true
代码
class Solution
{
public:
bool checkrow[9][10];
bool checkcol[9][10];
bool gird[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] != '.')
{
int nums = board[i][j] - '0';
checkcol[j][nums] = checkrow[i][nums] = gird[i/3][j/3][nums] = true;
}
}
}
dfs(board);
}
// 可以遍历所有空的位置的不需要row传参过来
bool dfs(vector<vector<char>>& nums)
{
for(int row = 0;row < 9;row++)
{
for(int col = 0;col < 9;col++)
{
if(nums[row][col] == '.')
{
for(char i = '1';i <= '9';i++)
{
int data = i - '0';
if(!checkcol[col][data] && !checkrow[row][data] && !gird[row/3][col/3][data])
{
nums[row][col] = i;
checkcol[col][data] = checkrow[row][data] = gird[row/3][col/3][data] = true;
if(dfs(nums) == true) return true;// 如果这个位置填完了返回了true,就不要再试下一个i了
// 恢复现场
nums[row][col] = '.';
checkcol[col][data] = checkrow[row][data] = gird[row/3][col/3][data] = false;
}
}
// 可能出现填不了的情况,1到9都不行
return false;
}
}
}
// 空位置全都填完了,返回true
return true;
}
};
单词搜索
题解
1. 画出决策树
2. 全局变量：m，n矩阵的大小，vis数组标记这个格子已经走过了
3. 剪枝：如果找不到第一个匹配的字符就剪枝
4. 回溯：如果找不到下一个匹配的字符就回溯
5. 递归出口：pos是字符串的长度，如果匹配到越界就说明找到了
6. 函数头：i，j是匹配到第一个字符的坐标，s是字符串，pos是匹配的字符的位置，board是矩阵
7. 利用向量找i，j的上下左右，就不需要用四个for循环了
代码
class Solution
{
public:
int m,n;
// 标记该点是否使用过了
bool vis[7][7];
bool exist(vector<vector<char>>& board, string word)
{
m = board.size();
n = board[0].size();
for(int i = 0;i < m;i++)
{
for(int j = 0;j < n;j++)
{
if(board[i][j] == word[0])
{
vis[i][j] = true;
if(dfs(board,i,j,word,1)) return true;
vis[i][j] = false;
}
}
}
// 都没找到匹配的字符串
return false;
}
// 上下左右四个坐标
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
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 = i + dx[k],y = j + dy[k];
if(x >= 0 && x < m && y >= 0&&y < n && !vis[x][y] && board[x][y] == word[pos])
{
vis[x][y] = true;
if(dfs(board,x,y,word,pos+1)) return true;
vis[x][y] = false;
}
}
// 说明i,j位置找不到,是错误的位置
return false;
}
};
黄金矿工
题解
1. 跟上一题非常类似，唯一要注意的是递归出口是可以每次更新的，因为写递归出口需要判断用for循环每次去更新比较麻烦
2. 可以使用path在参数中，dfs(path + gird[x][y])，这样每次加就不需要手动恢复现场了，函数会帮我们自动恢复现场，每次更新结果在dfs的开头，虽然多更新几次，但是不太麻烦
3. 我写的是全局的变量，需要恢复现场
代码
class Solution
{
public:
bool vis[16][16];
int m,n;
int ret = 0;
int ans;
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)
{
// 避免重复使用这个位置
vis[i][j] = true;
ans += grid[i][j];
dfs(grid,i,j);
ret = max(ans,ret);
vis[i][j] = false;
ans -= grid[i][j];
}
}
}
return ret;
}
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
void dfs(vector<vector<int>>& grid,int i,int j)
{
for(int k = 0;k < 4;k++)
{
int x = dx[k] + i,y = dy[k] + j;
if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y]!= 0)
{
vis[x][y] = true;
ans += grid[x][y];
dfs(grid,x,y);
ret = max(ans,ret);
vis[x][y] = false;
ans -= grid[x][y];
}
}
}
};
不同路径
题解
1. 这题要注意的一点是设计一个全局变量count，用来统计0的个数，在参数中多一个step，如果step和count相同，并且这个点的值是2，那么就是一个路径
2. 这题和上题也非常相似
代码
class Solution
{
public:
// 统计0的个数
int count;
bool vis[21][21];
int m,n;
int ans;
int uniquePathsIII(vector<vector<int>>& grid)
{
// 初始化为局部变量了,符了
m = grid.size(),n = grid[0].size();
int dx,dy;
for(int i = 0;i < m;i++)
{
for(int j = 0;j < n;j++)
{
if(grid[i][j] == 0) count++;
else if(grid[i][j] == 1)
{
dx = i;
dy = j;
}
}
}
grid[dx][dy] = true;
dfs(grid,dx,dy,0);
return ans;
}
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 step)
{
if(count == step && grid[i][j] == 2)
{
ans++;
return;
}
for(int k = 0;k < 4;k++)
{
int x = dx[k] + i,y = dy[k] + j;
if(x >= 0 && x < m && y >= 0&& y < n && !vis[x][y] && grid[x][y] == 0)
{
vis[x][y] = true;
dfs(grid,x,y,step + 1);
vis[x][y] = false;
}
if(count == step&&x >= 0 && x < m && y >= 0&& y < n && !vis[x][y] && grid[x][y] == 2)
{
vis[x][y] = true;
dfs(grid,x,y,step);
vis[x][y] = false;
}
}
}
};
总结
1. 题目识别什么时候用矩阵搜索？
当出现向上，向下，向左，向右搜索时可以使用
2. 怎么使用矩阵搜索？
上面的三题里做了，就是模版
3. 如果是矩阵填空的题怎么做，例如N皇后？
可以用bool数组标记填过的行列斜对角线检查是否有效，然后一层一层去搜索，这种题主要也是画决策树，就是多了几个bool数组检查使用过的格子，之后不再使用这个格子