1 bfs廣度優(yōu)先搜索

1.1 是什么

1.2怎么實現(xiàn)

2案例學(xué)習(xí)

2.1.走迷宮

?2.2.P1443 馬的遍歷

2.3.?九宮重排（看答案學(xué)的，實在寫不來）

?2.4.青蛙跳杯子（學(xué)完九宮重排再做bingo）

2.5. 長草

?3.總結(jié)

---

1 bfs廣度優(yōu)先搜索

【Python搜索算法】廣度優(yōu)先搜索（BFS）算法原理詳解與應(yīng)用，示例+代碼_廣度優(yōu)先算法的路徑搜索代碼-CSDN博客

1.1 是什么

? ? ? ? 看了其他大佬的分享之后，我理解的廣度優(yōu)先搜索是一種圖遍歷的算法，簡單來說是他的訪問規(guī)則是一層一層的訪問，先訪問距離節(jié)點近的數(shù)據(jù)，再逐層拓展訪問遠的數(shù)據(jù)。與廣度優(yōu)先搜索密切相關(guān)的數(shù)據(jù)類型叫做隊列。隊列我們可以理解為是日常生活中排隊所形成的隊形，先進先出是隊列最大的特點。

1.2怎么實現(xiàn)

BFS算法的步驟如下：

1. 初始化：選擇一個起始節(jié)點，將其標(biāo)記為已訪問，并將其放入隊列中（作為起始節(jié)點）。
2. 進入循環(huán)：重復(fù)以下步驟，直到隊列為空。 a. 從隊列中取出一個節(jié)點。 b. 訪問該節(jié)點。 c. 將所有未訪問的相鄰節(jié)點加入隊列。 d. 標(biāo)記已訪問的節(jié)點，以避免重復(fù)訪問。
3. 結(jié)束循環(huán)：當(dāng)隊列為空時，表示已經(jīng)遍歷完整個圖。

算法原理：

? ? ? ? BFS的工作原理是通過隊列數(shù)據(jù)結(jié)構(gòu)來管理待訪問的節(jié)點。它從起始節(jié)點開始，然后逐一訪問該節(jié)點的相鄰節(jié)點，并將它們加入隊列。然后，它從隊列中取出下一個節(jié)點進行訪問，以此類推。這確保了節(jié)點按照它們的距離從起始節(jié)點逐層遍歷，因此BFS可以用于查找最短路徑。

? ? ? ? BFS是一個寬度優(yōu)先的搜索，它在查找最短路徑等問題中非常有用。它不會陷入深度過深的路徑，因為它會優(yōu)先探索距離起始節(jié)點更近的節(jié)點。

總結(jié)：廣度優(yōu)先搜索一般來說都會有一個隊列去存儲節(jié)點，同時也會有一個數(shù)組去記錄訪問的狀態(tài)。?

2案例學(xué)習(xí)

2.1.走迷宮

輸入：

5 5 
1 0 1 1 0
1 1 0 1 1 
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5 

輸出：

8

?????????說明一下這道題的思路，這道題非常直觀體現(xiàn)了BFS，并且是最基本的BFS。那代碼的思路是怎么樣的呢？我們來捋一下。

? ? ? ? 一開始所說的隊列其實就是列表，只是用到了隊列的特點，也就是說隊列其實就是類似于列表，只是這個算法的思路用到了隊列的特點，一開始我想得太復(fù)雜了，總以為隊列是一個很高級的容器，其實簡單理解就是列表。

? ? ? ? 那根據(jù)BFS的算法思路：

1. 初始化：將迷宮的起點作為起始節(jié)點????????queue=[(x1-1,y1-1,step)]
2. 進入循環(huán)：循環(huán)終止的條件是什么，當(dāng)列表為空就終止了? ? ???while queue:? ? ? ? ? ? ? ? ? ? 怎么取出列表的第一個元素，這個時候就是隊列的特點，先進先出，怎么體現(xiàn)在列表中，進去就是存入，出來就是刪除? ? ? x,y,step=queue.pop(0)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? 這里頁需要注意走迷宮有上下左右四個方向?qū)?yīng)的就是坐標(biāo)的變化，這也是我對子節(jié)點的一個理解

? ? ? ? ?同時已經(jīng)訪問過的點也要做好標(biāo)記

????????我當(dāng)時還有一個特別想不懂的，哈哈哈哈哈哈，想起來感覺自己特別蠢哈哈哈哈哈。

????????怎么著，我想著每一個節(jié)點都有四個子節(jié)點，那意味著線路會不一樣，怎么就知道那一個的step是最小的，結(jié)果我看到那個判斷的出口就一下子大悟了，最短路徑嘛，那早點滿足出口條件的不就是最短路徑嘛

n, m = map(int,input().split())
data = []
d = [[1,0],[-1,0],[0,1],[0,-1]]
for i in range(n):l = list(map(int,input().split()))data.append(l)
x1, y1, x2, y2 = map(int,input().split())
def bfs(x1,y1,step):queue=[(x1-1,y1-1,step)]while queue:x,y,step=queue.pop(0)if x==x2-1 and y==y2-1:return stepfor xx,yy in d:dx = x+xxdy = y+yyif 0<= dx <n and 0<= dy <m and data[dx][dy] :data[dx][dy]=0queue.append((dx,dy,step+1))return -1
print(bfs(x1,y1,0))

?2.2.P1443 馬的遍歷

做好久了但是還是沒有完全通過，怎么辦可以幫忙看看嘛?

n, m, x, y= map(int,input().split())
d = [[-1,2],[-2,1],[-2,-1],[-1,-2],[1,2],[2,1],[2,-1],[1,-2]]
data = []
result = [[0 for _ in range(m)]for _ in range(n)]
for i in range(1,n+1):for j in range(1,m+1):data.append([i,j])
from collections import deque
def bfs(x,y,a,b,step,visit):queue = deque([(x,y,step)])while len(queue) != 0:x1, y1, step = queue.popleft()if x1 == a and y1 == b:return stepfor xx,yy in d:dx = x1+xxdy = y1+yyif dx < 1 or dx > n or dy < 1 or dy > m:continueif visit[dx][dy] == 0:visit[dx][dy] = 1queue.append((dx, dy, step + 1))return -1for i,j in data:visit = [[0 for _ in range(m + 1)] for _ in range(n + 1)]visit[x][y] = 1ans = bfs(x,y,i,j,0,visit)result[i-1][j-1] = ans
for i in result:for j in i:print(j,end='\t')print('\n',end='')

2.3.?九宮重排（看答案學(xué)的，實在寫不來）

6.九宮重排 - 藍橋云課 (lanqiao.cn)

????????我當(dāng)時自己做的時候就在糾結(jié)到底是移動格子還是移動數(shù)字，很顯然，如果要移動數(shù)字那每個數(shù)字都需要移動，但是移動格子的話我們只需要對這個格子進行操作就可以了。所以移動格子是最佳方案。

?????????以下是我自己寫的錯誤代碼，真的是錯的離譜，紀(jì)念一下我稀里糊涂的腦子

start = input()
end = input()map1 = [[0 for _ in range(3)] for _ in range(3)]
map2 = [[0 for _ in range(3)] for _ in range(3)]
k1, k2 = 0, 0
for i in range(3):for j in range(3):map1[i][j] = start[k1]if start[k1] == '.':a, b = i, jk1 += 1
for i in range(3):for j in range(3):map2[i][j] = end[k2]k2 += 1d = [[1,0],[-1,0],[0,1],[0,-1]]def bfs(a,b,step):global map1visit = [[0 for _ in range(3)] for _ in range(3)]queue = [(a,b,step)]visit[a][b] = 1while queue:x, y, step = queue.pop(0)if map1 == map2:return stepfor xx,yy in d:dx = x+xxdy = y+yyif dx<0 or dx>2 or dy<0 or dy>2:continueif visit[dx][dy] == 0:visit[dx][dy] = 1map1[x][y],map1[dx][dy] = map1[dx][dy],map1[x][y]queue.append((dx,dy,step+1))return -1
print(bfs(a,b,0))

?????????別人大佬的代碼代碼寫的真好

藍橋杯：九宮格重排【BFS】【Python】_重排九宮問題bfs-CSDN博客

????????當(dāng)然我在別人的代碼上加上了一些修改以及注釋，主要是得自己看得懂

????????我也反思了一下自己寫的代碼思路和別人的，我在一維和二維的變換上處理的十分混亂，導(dǎo)致自己都不知道到底是個什么事兒，因為我也知道是去移動格子，然后交換，但是我就很混亂。當(dāng)然我的思路還有一些錯誤。

? ? ? ? 別人的代碼思路這一點我真是沒想到，就是用字典的鍵值對去存儲每一次移動格子后所形成的新字符串的步數(shù)，一旦相等了就可以直接返回。

start = input()
end = input()from collections import deque
def bfs():# 創(chuàng)建容器并初始化# 創(chuàng)建字典存儲每次變換字符串的步數(shù)dic = {}dic[start] = 0# 創(chuàng)建隊列queue = deque()queue.append(start)d = [[1, 0], [-1, 0], [0, 1], [0, -1]]# 進入循環(huán)while queue:now_start = list(queue.popleft())# 循環(huán)結(jié)束出口if "".join(now_start) == end:return dic["".join(now_start)]point = now_start.index('.')# 一維的下標(biāo)轉(zhuǎn)換為二維下標(biāo)：# 轉(zhuǎn)換公式：x = index//二維數(shù)組的寬度    y = index%二維數(shù)組的寬度x = point // 3y = point % 3step = dic["".join(now_start)]for xx,yy in d:dx = x+xxdy = y+yyif dx>=0 and dx<3 and dy>=0 and dy<3:new_start = now_start.copy()# 二維轉(zhuǎn)一維# 轉(zhuǎn)換公式：index = x*二維數(shù)組的寬度 + ynew_start[point],new_start[dx*3+dy] = new_start[dx*3+dy],new_start[point]if "".join(new_start) not in dic.keys():# dic.setdefault("".join(new_start),step+1)dic["".join(new_start)] = step+1queue.append("".join(new_start))return -1print(bfs())

?

?知識點筆記：

?2.4.青蛙跳杯子（學(xué)完九宮重排再做bingo）

1.青蛙跳杯子 - 藍橋云課 (lanqiao.cn)

????????那學(xué)完九宮重排之后寫這道題就非常簡單了，并且這道題還是一維的，不用轉(zhuǎn)換，其他思路跟九宮重排一模一樣。

????????題目中所說的三種動作，雖然說是青蛙的跳動，但是把當(dāng)作杯子的跳動去處理就會簡單很多，總之學(xué)完九宮重排之后這道題就是很簡單了。

start = input()
end = input()from collections import deque
def bfs():d = [1, -1, 2, -2, 3, -3]queue = deque()queue.append(start)dic = {}dic[start] = 0while queue:now_start = list(queue.popleft())point = now_start.index('*')step = dic["".join(now_start)]if "".join(now_start) == end:return dic["".join(now_start)]for xx in d:dx = point+xxnew_start = now_start.copy()if dx in range(0, len(start)):new_start[point], new_start[dx] = new_start[dx], new_start[point]if "".join(new_start) not in dic.keys():dic["".join(new_start)] = step+1queue.append("".join(new_start))return -1print(bfs())

2.5. 長草

0長草 - 藍橋云課 (lanqiao.cn)

????????這道題一開始的思路是想到了非連通圖的遍歷，然后我就是這么一個思路，先找到一個初始化的點先進行廣度優(yōu)先搜索，只進行K層的搜索，但是我一直都無法找到怎樣去把握讓搜索測層數(shù)是我想要的，不知道這個怎么解決，在這里遇到了大問題，然后再遍歷我的地圖看看還有沒有另外的點需要搜索的。所以這個思路就需要兩個數(shù)組，一個是隊列，一個是記錄我的訪問狀態(tài)，但是我并沒有解決。

????????然后就換了一個思路，將節(jié)點先依次入隊，再對每一個節(jié)點進行廣度優(yōu)先搜索，這個就比較好控制，多少層那我就調(diào)用多少次的bfs。這里有一個點就在于我的while循環(huán)的出口是與隊列的長度有關(guān)（或者是說節(jié)點的個數(shù)），因為隊列只有把所有的節(jié)點都遍歷完成之后才算。

? ? ? ? 總之這道題也是一道與之前有著一點區(qū)別的，也可以算作是遍歷非連通圖的一種方法。

n, m = map(int,input().split())
maps = []
for i in range(n):l = list(input())maps.append(l)
k = int(input())from collections import deque
queue = deque()
for i in range(n):for j in range(m):if maps[i][j] == 'g':queue.append((i,j))d = [[1,0],[-1,0],[0,1],[0,-1]]
def bfs():ans = len(queue)while ans:x1, y1 = queue.popleft()for xx,yy in d:dx = x1+xxdy = y1+yy# if dx<0 or dx>=n or dy<0 or dy>=m:#     continuif 0<=dx<n and 0<=dy<m and maps[dx][dy] == '.':maps[dx][dy] = 'g'queue.append((dx,dy))ans -= 1for i in range(k):bfs()
for i in maps:print(''.join(i))

?

?3.總結(jié)

學(xué)習(xí)還在繼續(xù)，持續(xù)學(xué)習(xí)加油！！！！