当前位置:网站首页>LeetCode 37. Solve Sudoku
LeetCode 37. Solve Sudoku
2022-08-09 13:49:00 【A pig to】
class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
pair<int,int> p = getNext(board);
int sx = p.first,sy = p.second;
dfs(sx,sy,board);
}
bool dfs(int x,int y,vector<vector<char>>& board){
if(isFinished(board)) {
return true;
}
for(int n=1;n<=9;n++){
board[x][y] = char(n+'0');
if(isValidSudoku(board)){
pair<int,int> p = getNext(board);
int sx = p.first,sy = p.second;
if(dfs(sx,sy,board)){
return true;
}
}
}
board[x][y] = '.';
return false;
}
pair<int,int> getNext(vector<vector<char>>& board) {
int sx=-1,sy=-1;
for(int i=0;i<9;i++){
if(sx!=-1){
break;
}
for(int j=0;j<9;j++){
if(board[i][j]=='.'){
sx = i, sy = j;
break;
}
}
}
return make_pair(sx,sy);
}
bool isFinished(vector<vector<char>>& board){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]=='.'){
return false;
}
}
}
return true;
}
bool isValidSudoku(vector<vector<char>>& board) {
bool rv[9][10]={
0},cv[9][10]={
0},gv[9][10]={
0};
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]=='.') {
continue;
}
int v = board[i][j]-'0';
if(rv[i][v] || cv[j][v] || gv[i/3*3+j/3][v]){
return false;
}
rv[i][v] = 1;
cv[j][v] = 1;
gv[ i/3*3+j/3 ][v] = 1;
}
}
return true;
}
};
边栏推荐
- Map mixed density function and quantile added line
- Uni - app - uview Swiper shuffling figure component, click on the links to jump (click to get the item after the row data, remove data operation)
- 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面(循环不变量)
- 我的2020年终总结
- 造自己的芯,让谷歌买单!谷歌再度开源 180nm 工艺的芯片
- 如何求最大公约数?
- WSA工具箱安装应用商店提示无法工作怎么解决?
- Rust 入门指南(使用JSON)
- [HCIP Continuous Update] Principle and Configuration of IS-IS Protocol
- Flutter Getting Started and Advanced Tour (8) Button Widget
猜你喜欢
从NPU-SLAM-EDA技术分析
绘制混合密度函数图以及添加分位数线
Clock frequency and baud rate count for serial communication in FPGA
GIN a preliminary study, the environment is installed
The sword refers to the offer, cuts the rope 2
乐东消防救援大队应邀为干部开展消防安全培训
GIN Bind mode to get parameters and form validation
jenkins api创建自定义pipeline
联通网管协议框图
Oracle Recovery Tools修复空闲坏块
随机推荐
Clock frequency and baud rate count for serial communication in FPGA
LnReader编译
5G China unicom repeater network management protocol real-time requirements
2.微服务'黑话'集锦及Eureka注册中心相关概念
Flutter entry and advanced tour (6) Layout Widget
时间序列分析课程实验报告
Oracle Recovery Tools修复空闲坏块
ERP不规范,同事两行泪 (转载非原创)
安踏携手华为运动健康共同验证冠军跑鞋 创新引领中国体育
ftplib+ tqdm upload and download progress bar
FFMPEG多媒体文件处理(ffmpeg文件的删除与重命名)
某高校的R语言数据分析期末作业
2022年非一线IT行业就业前景?
leetcode 20. Valid Parentheses 有效的括号(中等)
工作任务统计
陈强教授《机器学习及R应用》课程 第十四章作业
glibc 内存管理模型 释放 C库内存缓存
JVM之配置介绍(一)
GIN Bind mode to get parameters and form validation
GIN中GET POST PUT DELETE请求