AcWing 3190. 路径之谜——python
原题链接
简单
作者:
JSJBY
,
2024-04-12 21:25:35
,
所有人可见
,
阅读 2
import os
import sys
n=int(input())
st=[False]*(n*n+100)#是否走过
col=list(map(int,input().split()))#列
row=list(map(int,input().split()))#行
al=sum(col)+sum(row)
dx=[-1,0,1,0]
dy=[0,-1,0,1]
pt=''
def dfs(x,y,path):
global pt
col[x]-=1
row[y]-=1
st[(y-1)*n+x-1]=True
if col[x]==0:
for i in range(x):
if col[i]!=0:return
if row[y]==0:
for i in range(y):
if row[i]!=0:return
if x==n-1 and y==n-1 and sum(col)==0 and sum(row)==0:
pt=path
return
for i in range(4):
newx=dx[i]+x
newy=dy[i]+y
if newx>=0 and newx<n and newy>=0 and newy<n and not st[(newy-1)*n+newx-1] and col[newx]>0 and row[newy]>0:
dfs(newx,newy,path+"/"+str((newy)*n+newx))
col[newx]+=1
row[newy]+=1
st[(newy-1)*n+newx-1]=False
dfs(0,0,'0')
for i in pt.split("/"):
print(i,end=" ")