BFS 최 단 로 를 구하 세 요.

/ * n 행 m 열의 미로 가 있다 고 가정 하면 각 단 위 는 공 터 (1 로 표시) 또는 장애물 (0 으로 표시) 입 니 다. 예 를 들 어 출발점 에서 종점 까지 의 가장 짧 은 경 로 를 찾 습 니까?BFS 검색 을 이용 하여 각 노드 에서 출발점 까지 의 최 단 거리 와 최 단 경로 각 노드 의 앞 노드 를 점차적으로 계산 합 니 다.마지막 으로 시작 점 을 뿌리 로 하 는 BFS 트 리 가 생 성 됩 니 다.이때 BFS 는 임의의 지점 에서 기점 까지 의 거 리 를 구 할 수 있 습 니 다. * /그림 1 3 0 21 23 2 0 17 20 22 4 0 14 0 5 0 12 18 6 10 19 7 9 11 13 16
입력 6, 5, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1.
출력
코드

#include
#include
#include
#include
#include
using namespace std;
const int maxn=100+5;

int G[maxn][maxn];   //   d=id
int path[maxn];      //         ，   
int n,m;             //n    m 
int k=1;//    
int end_num;
int vx[5] = {-1,1,0,0};   //vx  vy              4   
int vy[5] = {0,0,-1,1};
bool vis[maxn][maxn];     //             

struct node
{
    int x;
    int y;
    int id;
    int parent=0;
    node(int a,int b,int c)
    {
        x=a;
        y=b;
        id=c;
    }
};

int main()
{
    //freopen("in.txt","r",stdin);
    memset(G,0,sizeof(G));
    memset(vis,0,sizeof(vis));
    memset(path,0,sizeof(path));
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            cin>>G[i][j];
        }
    queue<node> q;
    node v=node(1,1,1);
    q.push(v);
    vis[1][1]=1;
    while(!q.empty())
    {
        node u=q.front();
        q.pop();
        path[u.id]=u.parent;//         
        for(int i=0; i<4; i++)
        {
            int tx=u.x+vx[i];
            int ty=u.y+vy[i];
            if(G[tx][ty]&&!vis[tx][ty])//        
            {
                vis[tx][ty]=1;
                //cout<
                node v=node(tx,ty,++k);
                end_num=k;
                v.parent=u.id;
                q.push(v);
            }
        }
    }
    vector<int> ans;
    //cout<
    while(end_num)//          
    {
        ans.push_back(end_num);
        end_num=path[end_num];
    }
    int s=0;
    while(!ans.empty())
    {
        s++;
        cout<<*(ans.end()-1)<<' ';//ans       0
        ans.pop_back();
    }
    cout<<endl<<s-1;
    return 0;
}