华为机试-迷宫问题

本算法采用深度优先遍历思想(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;
}