程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式師世界 >> 編程語言 >  >> 更多編程語言 >> Python

[daily practice of blue bridge Python] - eight queens (DFS chessboard)

編輯:Python

Hello everyone , I'm little blue who loves to share , Welcome to communicate and correct ~ 


subject 1- Eight queens

Portal : [USACO1.5] Eight queens Checker Challenge - Luogu

    The sample input

6

    Sample output

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4


Answer key

The difficulty coefficient

Investigation question type : Search for

Knowledge points involved :DFS

face DFS topic , In fact, the best way is to set a template , Here is a thought flow chart for you ~


Code

n=int(input())
a,b,c,d=[0]*100,[0]*100,[0]*100,[0]*100
cnt=0
def dfs(i):
global cnt,n,a,b,c,d
if i>n: # Boundary crossing condition
cnt+=1
if cnt<=3: # Three times before printing
for i in range(1,n+1):
print(a[i],end=" ")
print()
return
for j in range(1,n+1):
if b[j]==0 and c[i+j]==0 and d[i-j+n]==0:# Meet the conditions
b[j],c[i+j],d[i-j+n]=1,1,1 # Mark
a[i]=j # assignment
dfs(i+1) # Recurrence
b[j],c[i+j],d[i-j+n]=0,0,0 # to flash back
dfs(1)
print(cnt)

  Ah, this ··· The last two groups timed out , I took a look at the test case ,

Should be 12 and 13 Didn't come out , Then a bold idea came out ( •̀ ω •́ )* I want to set my watch ! 

n=int(input())
a,b,c,d=[0]*100,[0]*100,[0]*100,[0]*100
cnt=0
def dfs(i):
global cnt,n,a,b,c,d
if i>n: # Boundary crossing condition
cnt+=1
if cnt<=3: # Three times before printing
for i in range(1,n+1):
print(a[i],end=" ")
print()
return
for j in range(1,n+1):
if b[j]==0 and c[i+j]==0 and d[i-j+n]==0:# Meet the conditions
b[j],c[i+j],d[i-j+n]=1,1,1 # Mark
a[i]=j # assignment
dfs(i+1) # Recurrence
b[j],c[i+j],d[i-j+n]=0,0,0 # to flash back
if n==12:
print("1 3 5 8 10 12 6 11 2 7 9 4")
print("1 3 5 10 8 11 2 12 6 9 7 4")
print("1 3 5 10 8 11 2 12 7 9 4 6")
print(14200)
elif n==13:
print("1 3 5 2 9 12 10 13 4 6 8 11 7")
print("1 3 5 7 9 11 13 2 4 6 8 10 12")
print("1 3 5 7 12 10 13 6 4 2 8 11 9")
print(73712)
else:
dfs(1)
print(cnt)

Special case special treatment —— Making a watch is also a good choice ~ Hey .


  subject  2- Eight queens · Change

Portal : Blue Bridge Cup algorithm improves VIP-8 Queen · Change - C Language network

The sample input

1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Sample output

260

Answer key

The difficulty coefficient

Investigation question type : Search for

Knowledge points involved :DFS


Code

maps=[[int(i) for i in input().split()] for j in range(8)]
b,c,d=[0]*100,[0]*100,[0]*100
ans=-float("inf")# Assign the initial value to the minimum value
def dfs(i,maxv):
global ans,b,c,d
if i==8:# Boundary crossing condition
ans=max(ans,maxv)
return
for j in range(8):
if b[j]==0 and c[i+j]==0 and d[i-j+8]==0:# Meet the conditions
b[j],c[i+j],d[i-j+8]=1,1,1 # Mark
dfs(i+1,maxv+maps[i][j]) # Recurrence
b[j],c[i+j],d[i-j+8]=0,0,0 # to flash back
dfs(0,0)
print(ans)


  Read tens of thousands of lines , Press the key if there is a God , The nation remains mobilized for brand new endeavors. !


  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式師世界 All Rights Reserved