欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

SSL-ZYC 1455 电子老鼠闯迷宫

程序员文章站 2023-12-24 20:43:51
...

题目大意:
如下图12×12方格图,找出一条自入口(2,9)到出口(11,8)的最短路径。
SSL-ZYC 1455 电子老鼠闯迷宫


思路:
这道题我一开始想用DFS,但是很有可能超时。所以我这个可怜的 DFS党只能硬着头皮打BFS。

这道题把起点看作根,终点看成叶子结点,每次往上下左右四个方向找路,最终到了终点再递归回去输出答案。


代码:

#include<iostream>
#include<cstdio>
using namespace std;
int f[145],s[3][145],xx,yy,wx,wy,n,a[30][30],ok,last,best;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};


void p(int x)  //递归不解释 
{
    if (x==0) return;
    p(f[x]);
    best++;
    if (s[1][x]!=wx||s[2][x]!=wy) cout<<"("<<s[1][x]<<","<<s[2][x]<<")->";
                             else cout<<"("<<s[1][x]<<","<<s[2][x]<<")";
}


void bfs()
{
    int tail,head,k,i;
    head=0;
    tail=1;
    s[1][1]=xx;
    s[2][1]=yy;
    f[1]=0;  //初始化 
    do
    {
        head++;
        for (i=0;i<4;i++)
         {
            int x=s[1][head]+dx[i];  //x表示行 
            int y=s[2][head]+dy[i];  //y表示列 
            if (x>=1&&x<=n&&y>=1&&y<=n&&!a[x][y])  //如果该点没有走过并且没超界 
            {
                tail++;
                f[tail]=head;  //入队 
                s[1][tail]=x;  //x轴移动 
                s[2][tail]=y;  //y轴移动 
                a[x][y]=1;  //记录,防止死循环 
                if (x==wx&&y==wy)  //如果到达终点 
                {
                    p(tail);  //递归输出 
                    printf("\n%d",best);
                    tail=0;
                    break;
                }
            }
         }
    }
    while(head<tail);
}


int main()
{
    cin>>n;
    cin>>xx>>yy>>wx>>wy;
    for(int i=1;i<=n;i++)
     for (int j=1;j<=n;j++)
      cin>>a[i][j];
    bfs();  //开始BFS 
    return 0;  
}

上一篇:

下一篇: