当前位置: 首页 > article >正文

Leetcode 37 Sudoku Solver

题意

解决一个数独问题,有一个9*9 的矩阵,其中是字符'.'满足每一行每一列,以及每一个3 x 3的小块满足只有从1到9的字符,一定且仅有唯一的答案

题目链接

https://leetcode.com/problems/sudoku-solver/description/

思考

对于数独来说,对于每一个'.'格子而言,我都可以从1填到9,一共有81个格子,可以想像一颗有81层,每一个分支从1选到9的值。二维矩阵可以转化成一维来处理。
为什么这一题dfs要返回值?
因为如果是个void function,不返回true活着false,上一层函数就不知道信息。

我们举个例子
比如我需要从S走到E,如果不返回值,当找到一条正确路径的时候,上一层的dfs会擦除路径。void dfs会适合那种打印路径的问题。
S . .
X . .
. . E

思路

用dfs遍历所有非'.'的格子,从1填到9,当填完所有的81个格子时停下并且返回当前填空的状态。

class Solution {
public:
    int m = 0;
    int n = 0;
    void solveSudoku(vector<vector<char>>& g) {
        m = g.size();
        n = g[0].size();
        dfs(0, g);

    }

    bool dfs(int u, vector<vector<char>>& g) {
        if ( u == m * n) {
            return true;
        }
        int x = u / m;
        int y = u % m;
        if(g[x][y] != '.') {
            return dfs(u+1, g);
        } else {
            for(int i = 1; i <= 9; i++) {
                g[x][y] = i + '0';
                if(check(x,y, g) && dfs(u+1, g)) {
                    return true;
                }
                g[x][y] = '.';
            }
        }
        return false;
    }

    bool check(int x, int y, vector<vector<char>>& g) {
        char c = g[x][y];
        for(int i = 0; i < 9; i++) {
            if(i != x && g[i][y] == c) return false;
            if(i != y && g[x][i] == c) return false;
            int row = x/3*3 + i/3;
            int col = y/3*3 + i%3;
            if(x!= row && y != col && g[row][col] == c) return false;
        }
        return true;
    }
    
};

时间复杂度: O ( 9 81 ) = O ( 1 ) O(9^{81}) = O(1) O(981)=O(1)
空间复杂度: O ( 1 ) O(1) O(1)


http://www.kler.cn/a/447895.html

相关文章:

  • C++进阶-2-STL
  • 全脐点曲面当且仅当平面或者球面的一部分
  • 【IoTDB 线上小课 10】为什么选择 IoTDB 管理时序数据?
  • 圣诞快乐(h5 css js(圣诞树))
  • Vue3组件封装技巧与心得
  • *【每日一题 基础题】 [蓝桥杯 2023 省 B] 飞机降落
  • FastJSON 默认不会包含值为 null 的字段
  • C 语言实现四旋翼飞行器姿态控制:基于 PID 控制器(2)
  • 【前端js】 indexedDB Nosql的使用方法
  • Sourcegraph 概述
  • Redis篇--常见问题篇8--缓存一致性3(注解式缓存Spring Cache)
  • opencv项目--文档扫描
  • 3.metagpt中的软件公司智能体 (Architect 角色)
  • 纯血鸿蒙APP实战开发——文字展开收起案例
  • C# cad启动自动加载启动插件、类库编译 多个dll合并为一个
  • 图解HTTP-HTTP协议
  • 反归一化 from sklearn.preprocessing import MinMaxScaler
  • 2024年最新多目标优化算法:多目标麋鹿群优化算法(MOEHO)求解DTLZ1-DTLZ7及工程应用---盘式制动器设计,提供完整MATLAB代码
  • iframe和浏览器页签切换
  • 解决uniapp中使用axios在真机和模拟器下请求报错问题
  • 亚马逊API接口深度解析:如何高效获取商品详情与评论数据
  • 洛谷 P1644 跳马问题 C语言
  • (耗时4天制作)详细介绍macOS系统 本博文含有全英版 (全文翻译稿)
  • 【NLP 16、实践 ③ 找出特定字符在字符串中的位置】
  • 2024.12 迈向可解释和可解释的多模态大型语言模型:一项综合调查
  • JDK13主要特性