菜菜ccEL

用户名：uq_98515084648

访问量：2830

签　名：

等　　级
排　　名	2089
经　　验	2463
参赛次数	0
文章发表	30
年　　龄	0
在职情况	学生
学　　校
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

[编程入门]三个字符串的排序-JAVA题解
浏览：26

[编程入门]链表合并-JAVA题解
浏览：40

数据结构-链表的基本操作-JAVA实现题解
浏览：27

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （Java代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

蓝桥杯基础练习VIP-2n皇后问题-python(递归+回溯)-------------------超详细注释

　　作者: 菜菜ccEL　　　　发表时间：2022-04-06 20:16:22 浏览：144　|　评论：0　

原题链接：蓝桥杯基础练习VIP-2n皇后问题

n = int(input())
    li = [[0]*(n+1) for _ in range(n+1)]
	#从li[1][1]开始摆，将第一行第一列置0
    for i in range(n):
            tmp = list(map(int,input().split()))
            li[i+1][1:n+1] = tmp

w_queen = [0]*(n+1)	#w_queen[i]=j表示第i行第j列上放有白皇后
    b_queen = [0]*(n+1)	#b_queen[i]=j表示第i行第j列上放有黑皇后
    count=0		#计数
    
    def check(x,y,c):	#检查li[x][y]能否放置皇后,c表示皇后的颜色
            global w_queen,b_queen,li
            if li[x][y]==1:		#有空位
                    if c=='w':	检查的是白皇后
                            t = w_queen[:]	#t数组表示白皇后的分布情况
                    else:					#否则就为黑皇后
                            t = b_queen[:]
                    for i in range(1,x):	#从上往下遍历每行
                            if t[i]==y or (t[i]+i)==(x+y) or (i - t[i])==(x-y):		#如果y列上/右对角/左对角上已经放有对应皇后
                                    return False	#返回Flase
                    else:		#否则返回True
                            return True
    
    def dfs_b(row):
            global count,b_queen,n
            if row==n+1:	#黑皇后也摆满了
                    count+=1	#计数器+1
                    return
            for j in range(1,n+1):
                    if check(row,j,'b'):
                            before = li[row][j]
                            li[row][j] = 'b'
                            b_queen[row]=j
                            dfs_b(row+1)
                            b_queen[row]=0
                            li[row][j] = before
    
    def dfs_w(row):
            global w_queen,n
            if row==n+1:	#如果摆满白皇后
                    return dfs_b(1)	#接着从第一行开始摆黑皇后
            for j in range(1,n+1):	#逐列遍历 寻找第row行白皇后应该摆在哪一列
                    if check(row,j,'w'):	#如果该位置可以摆放
                            before = li[row][j]		#先把棋盘原本的值存起来，便于回溯
                            li[row][j] = 'w'	#在棋盘row行j列处放置白皇后
                            w_queen[row] = j	#标记row行的皇后放在j列上
                            dfs_w(row+1)	#递归寻找下一行皇后的摆放位置
                            w_queen[row]=0	回溯
                            li[row][j] = before
                            
    #先摆白皇后(或先摆黑皇后都可以)
    dfs_w(1)	#从第一行开始 一行一行摆放皇后
    print(count)

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

菜菜ccEL

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （Java代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【绝对值排序】（C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

简单的a+b （C语言代码）

蓝桥杯基础练习VIP-2n皇后问题-python(递归+回溯)-------------------超详细注释

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （Java代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

格式化数据输出（C语言代码）

输出九九乘法表（C语言代码）

陶陶摘苹果2 （C语言代码）

菜菜ccEL

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （Java代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【绝对值排序】 （C语言代码）

A+B for Input-Output Practice (VI) （C语言代码）

简单的a+b （C语言代码）

蓝桥杯基础练习VIP-2n皇后问题-python(递归+回溯)-------------------超详细注释

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （Java代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

格式化数据输出 （C语言代码）

输出九九乘法表 （C语言代码）

陶陶摘苹果2 （C语言代码）

【绝对值排序】（C语言代码）

　　评论区

格式化数据输出（C语言代码）

输出九九乘法表（C语言代码）