華爲機試-迷宮問題

本算法採用深度優先遍歷思想(DFS）,由於深度優先遍歷迷宮可能會有多種結果，因此需要保存每次成功的路徑，最後選擇最短路徑，代碼如下：

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> >path;//保存迷宮路徑 
vector<vector<int> >short_path;//保存最短迷宮路徑 
int N,M;
void display(vector<vector<int> >vt)
{
    for(vector<vector<int> >::iterator it=vt.begin();it!=vt.end();it++)
    {
        cout<<"("<<(*it)[0]<<","<<(*it)[1]<<")"<<endl;
    }
}
void find_path(vector<vector<int> >maze,int x,int y)
{
    maze[x][y]=1;
    path.push_back({x,y});
    if(x==N-1 && y==M-1)
    {
        if(short_path.empty()|| path.size()<short_path.size())
            short_path=path;
    }
    if(x-1>=0 && maze[x-1][y]==0)
        find_path(maze,x-1,y);
    if(x+1<N && maze[x+1][y]==0)
        find_path(maze,x+1,y);
    if(y-1>=0 && maze[x][y-1]==0)
        find_path(maze,x,y-1);
    if(y+1<M && maze[x][y+1]==0)
        find_path(maze,x,y+1);
    maze[x][y]=0;//恢復現場供其他路徑使用 
    path.pop_back();//彈出死衚衕 
}
int main()
{
    vector<vector<int> >maze;
    while(cin>>N>>M)
    {
        maze=vector<vector<int> >(N,vector<int>(M));
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                cin>>maze[i][j];
            }
        }
        find_path(maze,0,0);
        display(short_path);
    }
    return 0;
}