欢迎访问 生活随笔!

生活随笔

当前位置: 首页 >

LeetCode 37 解数独

发布时间:2025/3/15 28 豆豆
生活随笔 收集整理的这篇文章主要介绍了 LeetCode 37 解数独 小编觉得挺不错的,现在分享给大家,帮大家做个参考.
  • 题目描述
  • 编写一个程序,通过填充空格来解决数独问题。一个数独的解法需遵循如下规则:数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
  • 题解
  • 深度优先搜索
  • 代码
  • class Solution { public:bool dfs(vector<vector<char>>& board,int index,int n,vector<vector<bool>>& row,vector<vector<bool>>& col,vector<vector<bool>>& squ,vector<pair<int,int>>& vec){if (index>=vec.size()) return true;int i=vec[index].first;int j=vec[index].second;for (int k=1;k<=n;k++){if (!row[i][k]&&!col[k][j]&&!squ[((i-1)/3)*3+(j-1)/3+1][k]){row[i][k]=true;col[k][j]=true;squ[((i-1)/3)*3+(j-1)/3+1][k]=true;board[i-1][j-1]=k+'0';if (dfs(board,index+1,n,row,col,squ,vec)) return true;board[i-1][j-1]='.';row[i][k]=false;col[k][j]=false;squ[((i-1)/3)*3+(j-1)/3+1][k]=false;}}return false;}void solveSudoku(vector<vector<char>>& board) {int n=board.size();if (n!=9) return ;vector<vector<bool>> row(n+1,vector<bool>(n+1)),col(n+1,vector<bool>(n+1)),squ(n+1,vector<bool>(n+1));vector<pair<int,int>> vec;for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (board[i-1][j-1]!='.'){row[i][board[i-1][j-1]-'0']=true; // i行中已经有该数了col[board[i-1][j-1]-'0'][j]=true; // j列中已经有该数了squ[((i-1)/3)*3+(j-1)/3+1][board[i-1][j-1]-'0']=true; // 3*3宫内已经有该数了}else{vec.push_back({i,j});}}}dfs(board,0,n,row,col,squ,vec);} };

    总结

    以上是生活随笔为你收集整理的LeetCode 37 解数独的全部内容,希望文章能够帮你解决所遇到的问题。

    如果觉得生活随笔网站内容还不错,欢迎将生活随笔推荐给好友。