top1编程
← 返回题目
题解

【提高】迷宫的路径

1 条题解

  • 0
    @ 2026-7-29 0:15:06
    #include <bits/stdc++.h>
    using namespace std;
    int n,m,p;
    char c[50][50];
    bool a[50][50];
    int r[50][3];
    int fx[5]={0,0,1,0,-1};
    int fy[5]={0,1,0,-1,0};
    bool direct=false;
    void print(int k)
    {
        direct=true;
        p++;
        cout<<p<<":";
        for(int i=1;i<k;i++)
        {
            cout<<r[i][1]<<","<<r[i][2]<<"->";
        }
        cout<<r[k][1]<<","<<r[k][2]<<endl;
    }
    void dfs(int k)
    {
        //使用k型
        int tx,ty;
        for(int i=1;i<5;i++)
        {
            tx=r[k-1][1]+fx[i];
            ty=r[k-1][2]+fy[i];
            if(tx>0&&ty>0&&tx<=n&&ty<=m&&c[tx][ty]=='o'&&a[tx][ty]==false)
            {
                a[tx][ty]=true;
                r[k][1]=tx;
                r[k][2]=ty;
                if(tx==n&&ty==m)
                {
                    print(k);
                }
                else
                {
                    dfs(k+1);
                }//递进
                a[tx][ty]=false;
            }
        }
    }
    int main()
    {
        cin>>n>>m;
        getchar();
        r[1][1]=1;
        r[1][2]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>c[i][j];
            }
        }
        a[1][1]=true;
        dfs(2);
        if(direct==false)
            cout<<"no"<<endl;
    }
    
    • 1