一、問題描述
一筆畫完就是從起始網(wǎng)格開始波附，也就是下圖中錦鯉喵所在的網(wǎng)格，用一筆劃過所有可以走(灰底)的網(wǎng)格昼钻，不能遺漏掸屡，也不能重復(fù)。下圖是微信小游戲一筆畫完第1350關(guān)的題目：
二然评、解題思路
利用DFS(深度優(yōu)先搜索)和BFS(廣度優(yōu)先搜索)算法找到所有的路徑仅财，利用基于多線程實現(xiàn)的計時器展示尋找路徑所用的時間，最終圖示所有的解碗淌。簡單說下兩個算法的區(qū)別：
DFS(Depth First Search)也就是深度優(yōu)先搜索盏求，也就是從起始網(wǎng)格開始，只要是還有可以去的網(wǎng)格亿眠，就一直走下去碎罚，直到走不通為止，然后再回溯到最近的一次選擇缕探，再往下走魂莫，直到遍歷完所有的路徑还蹲。
BFS(Breadth First Search)也就是廣度(寬度)優(yōu)先搜索爹耗，也就是從起始網(wǎng)格開始，首先搜索與之相鄰的網(wǎng)格谜喊，然后在搜索與這些網(wǎng)格相鄰的網(wǎng)格潭兽。換句話說，就是逐漸的向周圍擴散搜索斗遏。
兩者利用Python實現(xiàn)的區(qū)別：DFS一般利用遞歸實現(xiàn)山卦，因為涉及到回溯，實現(xiàn)較為復(fù)雜诵次。因為Python中對遞歸函數(shù)有調(diào)用次數(shù)的限制账蓉，因此需要自己實現(xiàn)尾遞歸優(yōu)化枚碗。對于BFS而言，實現(xiàn)比較簡單铸本，但是因為需要保存當前的所有路徑肮雨，當路徑較多時，占用的內(nèi)存空間較大箱玷，因此需要刪除一些不合理的路徑怨规。
從運行時間上而言，獲取一條路徑優(yōu)先選擇DFS锡足，獲取所有路徑BFS好于DFS波丰。但是當可走的網(wǎng)格數(shù)較大時，優(yōu)先選擇DFS舶得，因為BFS可能導(dǎo)致內(nèi)存負載超重掰烟。
三、Python3實現(xiàn)
利用numpy的數(shù)組形式來描述問題沐批，也就是不同性質(zhì)的網(wǎng)格給定不同的數(shù)值媚赖，便于繪圖。需要根據(jù)謎題題面珠插，自定義輸入數(shù)組的維數(shù)惧磺，以及起始網(wǎng)格的索引，不可走網(wǎng)格的索引捻撑。根據(jù)這些設(shè)置磨隘，生成相應(yīng)的二維數(shù)組，并利用matplotlib繪制出來顾患。下面以上面的謎題為例番捂，需要進行下面的設(shè)置：
# 豎直、水平方向網(wǎng)格的個數(shù)
Map_Height = 9
Map_Width = 7
# 起始網(wǎng)格和不能經(jīng)過的網(wǎng)格的索引
Start_Index = [1, 0]
Stone_Index = [[0, 3], [0, 6], [1, 6], [2, 6], [3, 1], [7, 1], [8, 3], [8, 5], [8, 6]]
上圖為題面的示意圖
根據(jù)題面信息繪制的圖江解。
下面說一下對路徑合理性的判斷设预，對于一筆畫完的問題，當走過的網(wǎng)格和不能走的網(wǎng)格犁河，把剩下可以走的網(wǎng)格分為不連通的兩部分時鳖枕，就可判斷當前的路徑是不合理的，也就沒有在這個路徑上繼續(xù)往下搜索的意義桨螺。下圖顯示了加入路徑合理性判斷后的情況對比：
關(guān)于兩種算法的實現(xiàn)宾符，尾遞歸的優(yōu)化以及基于多線程的計時器的實現(xiàn)，參見代碼注釋灭翔。
考慮到手動輸入題面信息的繁瑣魏烫，還實現(xiàn)了自動讀取謎題照片。當然對照片的質(zhì)量要求較高(屏幕截圖可以(下圖上，第1350關(guān)的題面截圖)哄褒，相機拍攝(下圖下)會有問題)稀蟋。
三、結(jié)果圖示
第1350關(guān)一共有108條路徑解法呐赡，上圖上展示了基于BFS方法的第16個糊治，上圖下展示基于DFS方法的第108個。獲取所有路徑前者耗時大約105秒罚舱，后者大約186秒井辜。
上圖是根據(jù)DFS，獲取的一條路徑以及所用時間管闷。
上圖上是根據(jù)題面截圖自動讀取出來的結(jié)果粥脚，上圖下是添加路徑后的結(jié)果。因為調(diào)用的是DFS方法包个，所以得到的結(jié)果和上圖是一樣的刷允。
點擊獲得更多趣味謎題。歡迎Follow碧囊，感謝Star!!! 掃描關(guān)注微信公眾號pythonfan树灶，獲取更多。
