DFS--求解迷宮問題- IT閱讀

DFS--求解迷宮問題. 2018-12-09 254. 問題：從（0,0）出發到（n-1,m-1）的路徑. 輸入：. 6 8 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 0 DFS--求解迷宮問題 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search DFS--求解迷宮問題 2018-12-09254 問題：從（0,0）出發到（n-1,m-1）的路徑 輸入： 6 8 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0  0 0 0 1 1 0 1 1  1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0  輸出： (0,0)(0,1)(1,1)(1,2)(1,3)(0,3)(0,4)(0,5)(1,5)(2,5)(3,5)(3,6)(4,6)(5,6)(5,7） 解題思路：就是dfs搜尋，起點是（0,0），終點是（n-1,m-1），如果到達終點就直接返回，否則遞迴dfs搜尋其上下左右四個方向的 點，這四個方向可用intmove[4][2]={{0,1},{1,0},{0,-1},{-1,0}};表示，四個方向要滿足一下條件才能被訪問，1就是未被訪問過visited[i][j]==0且是通道map[i][j]==0,才能訪問，注意因為求的是路徑，所以根據遞迴的特點先返回的是終點，所以可以用棧來存放，然後逐個pop就是正確的路徑順序了。

但是dfs求的不是最短的路徑，而bfs求的是最短路徑。

需要用到佇列。

總結： ①從起點開始dfs滿足條件將起點入棧 ②開始遍歷該點的四周（就像圖中的訪問到該點時，就要遍歷與其相連且未被訪問的點，滿足條件再dfs 只不過visited是一維陣列作為標記是否訪問過） ③：四周滿足條件的標記好已訪問再dfs，然後返回1； ④：就是不斷的pop。

直到棧為空 #include #include #include usingnamespacestd; typedefpairp; constintN=500; intvisited[N][N],map[N][N]; intdfs(intx,inty); intmove[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; intn,m; stack

s; intmain(){ cin>>n>>m; for(inti=0;i>map[i][j]; for(inti=0;i=0&&y1>=0&&visited[x1][y1]==0&&map[x1][y1]==0){ visited[x1][y1]=1; if(dfs(x1,y1)){ s.push(make_pair(x1,y1)); return1; } } } return0; } 相關文章 DFS--求解迷宮問題 模擬求解迷宮問題（DFS+BFS） 佇列的應用——求解迷宮問題 佇列應用2：求解迷宮問題，最短路徑 應用棧求解迷宮問題（C++實現） 資料結構——求解迷宮問題（棧） 【資料結構】遞迴求解迷宮問題 棧求解迷宮問題 求解:迷宮問題BFS方法 BFS求解迷宮問題 使用棧求解迷宮問題C++ 棧的應用—求解迷宮問題 回溯法求解迷宮問題 寬度優先搜索BFS，求解迷宮問題 利用深度優先搜尋演算法和廣度優先搜尋演算法解迷宮問題 分類導航 HTML/CSS HTML教程 HTML5教程 CSS教程 CSS3教程 JavaScript JavaScript教程 jQuery教程 Node.js教程 服務端 Python教程 Python3教程 Linux教程 Docker教程 Ruby教程 Java教程 JSP教程 C教程 C++教程 Perl教程 Go教程 PHP教程 正則表達式 資料庫 SQL教程 MySQL教程 PostgreSQL教程 SQLite教程 MongoDB教程 Redis教程 Memcached教程 行動端 IOS教程 Swift教程 Advertisement 三度辭典 Copyright©2016-2021IT閱讀  Itread01.comAllRightsReserved. 0.001291036605835