首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >dfs深度搜索模板

dfs深度搜索模板

原创
作者头像
CaesarChang张旭
修改2021-02-19 15:32:39
5130
修改2021-02-19 15:32:39
举报
文章被收录于专栏:悟道悟道
import java.util.Scanner;
 
/**
 * @Author CaesarChang张旭
 * @Date 2021/2/18  12:06 下午
 * @Version 1.0
 */
public class Main {
    public static void main(String[] args) {
        char table[][] = new char[9][9];
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < 9; i++) {
            table[i]=scanner.nextLine().toCharArray();
        }
 
        dfs(table, 0, 0);
 
    }
 
    private static void dfs(char[][] table, int x, int y) {
 
        if (x == 9) {
            printf(table);
            System.exit(0);
 
        }
        if (table[x][y] == '0') {
            for (int k = 1; k < 10; k++) {
                if (check(table, x, y, k)) {
                    table[x][y]= (char) ('0'+k);
                    dfs(table, x + (y + 1) / 9, (y + 1) % 9);
                }
            }
            table[x][y] = '0';//回溯
        }else{
            dfs(table, x + (y + 1) / 9, (y + 1) % 9);
        }
 
 
    }
 
    private static void printf(char[][] table) {
 
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
 
                System.out.printf("%c",table[i][j]);
            }
            System.out.println();
        }
    }
 
    private static boolean check(char[][] table, int i, int j, int k) {
        //检查行 & 列
        for (int l = 0; l < 9; l++) {
 
                if (table[i][l] == (char)('0' + k)) {
                    return false;
                }
                if (table[l][j] == (char)('0' + k)) {
                    return false;
                }
            }
 
 
        //检查小矩形
        for (int l = (i / 3) * 3; l < (i / 3 + 1) * 3; l++) {
            for (int m = (j / 3) * 3; m < (j / 3 + 1) * 3; m++) {
                if (table[l][m] == (char)('0' + k)) {
                    return false;
                }
            }
        }
        return true;
 
 
    }
}

里面的check()函数根据题意,自行改变    

输入数组行和列也是根据题意, 自行改变

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档