第一题

题目

给定一个输出n求其全排列

分析

  1. 对于一个数从第一步开始走是1 2 3…n
  2. 输出后发现程序不能执行只能回溯
  3. 第二次选择1，2，3….n,n-1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
n=3
vis  = [0 for i in range(100)]
result = [0 for i in range(100)]
def dfs(dp): # int
    if dp>n: # 大于n就是终止条件要输出了
        print(result[1],result[2],result[3]) 
        return 
    for i in range(1,n+1):
        if vis[i]==0:
            vis[i] = 1 # 证明已经探索过了
            result[dp] = i  #dp=1,2,3
            dfs(dp+1)  # 每一次往前探索一步
            vis[i]=0 #回溯回来清除标记不然没法进行接下来的选数

第二题

题目

设有一个N*N方格的迷宫，入口和出口分别在左上角和右上角，迷宫格子中分别放0和1，0表示可通，1表示不能通过，入口和出口处肯定是0，迷宫走的规则如下：从某一点开始，有8个方向可以走，前进方格中数字为0时代表可通形，为0时表示要另寻路径。找出所有从入口到出口的路径（走过的路不能重复）输出路径的总数，如果无法到达则输出0

分析

  1. 从起点向八个方向深搜，到达终点则方案数+1，最后输出即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ans=0
n = 3
a=[[0]*100 for _ in range(100)]
b=[[0]*100 for _ in range(100)]
sx=[0,0,1,1,1,-1,-1,-1]
sy=[1,-1,0,1,-1,0,1,-1]

def dfs2(s,t): # int
    if s==1 and t==n:
        ans+=1
        return
    for i in range(8):#8个方向
        x = s + sx[i] 
        y = t + sy[i]
        if x>0 and y>0 and x<=n and y<=5 and a[x][y]==0 and b[x][y]==0:
            b[x][y]=1
            dfs2(x,y)
            b[x][y]=0 # 回溯
    return