LeetCode 37. 解数独
原题链接
困难
作者:
linux_2019
,
2019-09-14 17:12:47
,
所有人可见
,
阅读 1060
C++ 代码
class Solution {
public:
bool col[9][9]={0}, row[9][9]={0},cell[3][3][9]={0};
bool dfs(vector<vector<char>> & board,int x,int y)
{
if(y==9) x++,y=0;
if(x==9) return 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]='1'+i;
row[x][i]=col[y][i]=cell[x/3][y/3][i]=1;
if(dfs(board,x,y+1)) return true;
row[x][i]=col[y][i]=cell[x/3][y/3][i]=0;
board[x][y]='.';
}
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
{
char ch= board[i][j];
if( ch != '.')
{
char t=ch-'1';
row[i][t]=col[j][t]=cell[i/3][j/3][t]=1;
}
}
dfs(board,0,0);
}
};