題目

牛客：

解題思路

經(jīng)典的回溯算法題。走迷宮時可以向上，向下，向左和向右尋找，尋找時只要不越界和那一點(diǎn)的位置的值為0就可以走通。 可以使用一個二維數(shù)組path_temp用來記錄尋找過程中的路徑，同時到達(dá)路徑出口時進(jìn)行判斷，確定返回的結(jié)果一定是一個最短的路徑，也就是用path_best保存

代碼

#include <iostream> #include <vector> using namespace std;int ROW;//迷宮的行 int COL;//迷宮的列void backtrack(int i,int j,vector<vector<int>>& maze,vector<vector<int>>& path_temp,vector<vector<int>>& path_best)//回溯 {//如果還沒有到達(dá)，就一直找尋出口maze[i][j]=1;//首先做出選擇，所謂做出選擇就是將此位置置為1，表示已經(jīng)走過path_temp.push_back({i,j});//加入一個路徑//注意先做選擇再判斷if(i==ROW-1 && j==COL-1)//表示已經(jīng)達(dá)到迷宮出口{if(path_best.empty() || path_temp.size() < path_best.size())//如果有更短的路徑path_best=path_temp;}//剩下就是四處尋找了，注意不要越界if(i-1>=0 && maze[i-1][j]==0)//向上backtrack(i-1, j, maze, path_temp, path_best);if(i+1<ROW && maze[i+1][j]==0)//向下backtrack(i+1, j, maze, path_temp, path_best);if(j-1>=0 && maze[i][j-1]==0)//向左backtrack(i, j-1, maze, path_temp, path_best);if(j+1<COL && maze[i][j+1]==0)//向右backtrack(i, j+1, maze, path_temp, path_best);//撤銷選擇，恢復(fù)現(xiàn)場maze[i][j]=0;path_temp.pop_back();}int main() {while(cin >> ROW >>COL){vector<vector<int>> maze(ROW,vector<int>(COL,0));//迷宮空間vector<vector<int>> path_temp;//用來記錄可以到的迷宮出口的一條路徑vector<vector<int>> path_best;//始終保存最優(yōu)解for(int i=0;i<ROW;i++){for(int j=0;j<COL;j++){cin>>maze[i][j];}}backtrack(0, 0, maze, path_temp, path_best);for(auto &i : path_best){cout<<'('<<i[0]<<','<<i[1]<<')'<<endl;}}}

總結(jié)

以上是生活随笔為你收集整理的回溯算法之迷宫问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。