dfs是把一堆东西塞到某一个地方,塞的时候要注意约束条件
这道题就是把1-9的数字塞进数独表格里面
约束条件是:一行1-9出现一次,一列1-9出现一次,一个3*3格子1-9出现一次
class Solution {
bool dfs(int rowidx, int colidx, vector<vector<char>>& board, vector<vector<bool>> rows, vector<vector<bool>> cols, vector<vector<bool>> grid)
{
if(colidx == board[0].size())
{
rowidx++;
colidx = 0;
}
if(rowidx == board.size())
return true;
if(board[rowidx][colidx] != '.')
{
if(dfs(rowidx, colidx + 1,board, rows, cols, grid))
return true;
return false;
}
else
{
for(int i = 1; i <= 9; i++)
{
if(grid[1 + 3*(rowidx/3) + colidx/3][i] ||rows[rowidx][i] || cols[colidx][i])
continue;
board[rowidx][colidx] = '0' + i;
grid[1 + 3*(rowidx/3) + colidx/3][i] = rows[rowidx][i] = cols[colidx][i] = true;
if(dfs(rowidx, colidx + 1,board, rows, cols, grid))
return true;
grid[1 + 3*(rowidx/3) + colidx/3][i] = rows[rowidx][i] = cols[colidx][i] = false;
board[rowidx][colidx] = '.';
}
return false;
}
}
public:
void solveSudoku(vector<vector<char>>& board) {
if(!board.size() || !board[0].size())
return;
int n = board.size(), m = board[0].size();
int total = 0;
vector<vector<bool>> rows(n, vector<bool>(9 + 1, false)), cols(m, vector<bool>(9 + 1, false));
vector<vector<bool>> grid(10, vector<bool>(9 + 1, false));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
if(board[i][j]!='.')
{
total++;
int val = board[i][j] - '0';
rows[i][val] = true;
cols[j][val] = true;
grid[1 + 3*(i/3) + j/3][val] = true;
}
}
}
if(total == m * n)
return;
dfs(0, 0, board, rows, cols, grid);
}
};
可以通过优化状态存储来节省空间:
第二次写题
创建了三个数组,分别用来存储,某一行某一个数字能不能用,某一列某一个数字能不呢用,某一个格子某一个数字能不能用。然后使用dfs的方式来进行搜索,如果搜索到了,那么填好的格子就可以用来返回了。我这个代码需要注意的是,我把输入的变成了_board,它返回的也应该是_board,所以最后有一步是_board = board
class Solution {
vector<vector<bool>> rows;
vector<vector<bool>> cols;
vector<vector<bool>> grids;
vector<vector<char>> board;
bool found;
void dfs(int x, int y)
{
// cout << x << ' ' << y << endl;
if(found) return;
if(y == 9)
{
y = 0;
x++;
}
if(x == 9)
{
found = true;
return;
}
if(board[x][y] != '.') dfs(x, y + 1);
else
{
for(int k = 1; k <= 9; k++)
{
char c = k + '0';
if(!rows[x][k]) continue;
if(!cols[y][k]) continue;
if(!grids[(x/3) * 3 + y/3][k]) continue;
board[x][y] = c;
rows[x][k] = false;
cols[y][k] = false;
grids[x/3 * 3 + y/3][k] = false;
dfs(x, y + 1);
if(found) return;
board[x][y] = '.';
rows[x][k] = true;
cols[y][k] = true;
grids[(x/3) * 3 + y/3][k] = true;
}
}
}
public:
void solveSudoku(vector<vector<char>>& _board) {
board = _board;
found = false;
rows = vector<vector<bool>>(10, vector<bool>(10, true));
cols = vector<vector<bool>>(10, vector<bool>(10, true));
grids = vector<vector<bool>>(10, vector<bool>(10, true));
for(int r = 0; r < board.size() ; r++)
{
for(int c = 0; c < board[0].size(); c++)
{
if(board[r][c] == '.') continue;
int dig = board[r][c] - '0';
rows[r][dig] = false;
cols[c][dig] = false;
grids[(r/3) * 3 + c/3][dig] = false;
}
}
dfs(0, 0);
_board = board;
}
};