蓝桥杯day7——DFS&&BFS

文章目录

DFS：深度优先搜索

其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.
DFS自带回溯，应用于枚举和存在性问题

例题

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式
共一行，包含一个整数 n。

输出格式
按字典序输出所有排列方案，每个方案占一行。

数据范围
1≤n≤7
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

n = int(input())

path = []
res = []

def backtrace(n, used) :
    global path
    global res
    if len(path) == n :
        res.append(path[:])
        return
    for i in range(1, n + 1) :
        if used[i] :
            continue
        used[i] = True
        path.append(i)
        backtrace(n, used)
        used[i] = False
        path.pop()
        
used = [False] * (n + 1)

backtrace(n, used)

for i in res :
    for j in i :
        print(j, end = " ")
    print()

n− 皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

蓝桥杯day7——DFS&&BFS-LMLPHP

现在给定整数 n，请你输出所有的满足条件的棋子摆法。

输入格式
共一行，包含整数 n。

输出格式
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后，输出一个空行。

注意：行末不能有多余空格。

输出方案的顺序任意，只要不重复且没有遗漏即可。

数据范围
1≤n≤9
输入样例：
4
输出样例：
.Q…
…Q
Q…
…Q.

…Q.
Q…
…Q
.Q…

import copy
n = int(input())

graph = [['.'] * n for _ in range(n)]

res = []

def check(row, col) :
    global graph
    global n
    for i in range(row) :
        if graph[i][col] == 'Q' :
            return False
    for i in range(min(row, col) + 1) :
        if graph[row - i][col - i] == 'Q':
            return False
    for i in range(min(row, n - col - 1) + 1) :
        if graph[row - i][col + i] == 'Q' :
            return False
    return True

def dfs(row, n) :
    global graph
    global res
    if row == n :
        res.append(copy.deepcopy(graph))
    for i in range(n) :
        if check(row, i) :
            graph[row][i] = 'Q'
            dfs(row + 1, n)
            graph[row][i] = '.'
dfs(0, n)

for i in res :
    for j in i :
        for k in j :
            print(k, end="")
        print()
    print()

BFS: 广度优先搜索

属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
找最优解：dp是其中特例
模板

queue que #用于宽搜
graph g
hash_map[] #用于存每一步的结果
que.push(root)
while len(que) != 0 :
	q = que.pop()
	if q exits path : #如果q存在通往下个节点的路
		do something #vertical sngx 题目逻辑，状态转移
		que.push(q)
		hash_map(graph, q) # 记录状态

例题

给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。

输入格式
第一行包含两个整数 n 和 m。

接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。

输出格式
输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围
1≤n,m≤100
输入样例：
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例：
8

import collections
n, m = map(int, input().split())
que = collections.deque()
g = []
d = [[-1] * m for _ in range(n)]
for i in range(n) :
    g.append(list(map(int, input().split())))
    
def BFS() :
    global g, n, m
    global d, que
    DIRC = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    d[0][0] = 0
    que.appendleft([0, 0])
    while len(que) != 0 :
        loc = que.pop()
        for i in range(4) :
            x = loc[0] + DIRC[i][0]
            y = loc[1] + DIRC[i][1]
            if 0 <= x < n and 0 <= y < m and d[x][y] == -1 and g[x][y] == 0:
                d[x][y] = d[loc[0]][loc[1]] + 1
                que.appendleft([x, y])
BFS()

print(d[n - 1][m - 1])

在一个 3×3 的网格中，1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。

例如：

1 2 3
x 4 6
7 5 8
在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x
例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式
输入占一行，将 3×3 的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8

输出格式
输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 −1。

输入样例：
2 3 4 1 5 x 7 6 8
输出样例
19

import collections


start = "".join(list(input().split()))

def BFS(start) :
    end = "12345678x"
    DIRC = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    que = collections.deque()
    d = {}
    d[start]  = 0
    que.appendleft(start)
    while len(que) != 0 :
        q = que.pop()
        distance = d[q]
        tmpq = list(q)
        if q == end :
            return distance
        indeX = q.index('x')
        x, y = indeX // 3, indeX % 3
        for i in range(4) :
            x1 = x + DIRC[i][0]
            y1 = y + DIRC[i][1]
            if (0 <= x1 < 3 and 0 <= y1 < 3) :
                tmpq[indeX], tmpq[x1 * 3 + y1] = tmpq[x1 * 3 + y1], tmpq[indeX]
                if d.get("".join(tmpq), -1) == -1 :
                    d["".join(tmpq)] = distance + 1;
                    que.appendleft("".join(tmpq))
                tmpq[indeX], tmpq[x1 * 3 + y1] = tmpq[x1 * 3 + y1], tmpq[indeX]
    return -1

print(BFS(start))

对于Python中列表切片的补充

一个完整的切片表达式包含两个“:”，用于分隔三个参数(start_index、end_index、step)。当只有一个“:”时，默认第三个参数step=1；当一个“:”也没有时，start_index=end_index，表示切取start_index指定的那个元素。
切片操作基本表达式：object[start_index:end_index:step]
step：正负数均可，其绝对值大小决定了切取数据时的‘‘步长”，而正负号决定了“切取方向”，正表示“从左往右”取值，负表示“从右往左”取值。当step省略时，默认为1，即从左往右以步长1取值。“切取方向非常重要！”“切取方向非常重要！”“切取方向非常重要！”，重要的事情说三遍！
start_index：表示起始索引（包含该索引对应值）；该参数省略时，表示从对象“端点”开始取值，至于是从“起点”还是从“终点”开始，则由step参数的正负决定，step为正从“起点”开始，为负从“终点”开始。
end_index：表示终止索引（不包含该索引对应值）；该参数省略时，表示一直取到数据“端点”，至于是到“起点”还是到“终点”，同样由step参数的正负决定，step为正时直到“终点”，为负时直到“起点”。

一颗菜籽