题解：P6207 [USACO06OCT] Cows on Skates G

· · 题解

1.前言

一道典型的迷宫搜索问题~

这道题有 DFS 和 BFS 两种做法。

2. DFS 做法

这道题要考虑 vis 的置 1 。

我们首先要意识到， vis 无需置 0 。在一般 DFS 中， DFS 函数 return 后，一切洗牌，重新开始，尘封以前的记忆， vis 自然归 0 （听上去有 10^8 点点的玄乎）。而迷宫问题不一样，如果你将它的记忆清除的像金鱼一样，那么它就可能绕圈圈，死循环，最终TLE……

所以， DFS 后不要置 0 ！

AC code：

#include<bits/stdc++.h> 
using namespace std;
int n,m,num=1;
int ans[10000][2],vis[120][80];
char a[120][80];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y)
{
    if(x==n&&y==m)
    { 
        for(int i=1;i<=num;i++) cout<<ans[i][0]<<' '<<ans[i][1]<<endl;
        return ;
    }
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i]; 
        if(nx&&ny&&nx<=n&&ny<=m&&!vis[nx][ny]&&a[nx][ny]=='.')
        {
            vis[nx][ny]=1;
            num++;
            ans[num][0]=nx;
            ans[num][1]=ny;
            dfs(nx,ny);
            num--;
            //不要置 0 !
        }
    }
}
int main()
{   
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }
    vis[1][1]=1;
    ans[1][0]=1;
    ans[1][1]=1;
    dfs(1,1);
    return 0;
}

3. BFS做法

如果你选择 BFS 做法，那么你就需要一个 res 数组，与队列 q 一样，也需要一个 node 类型的 struct 结构体打包两个元素 x 和 y 。

为啥呢？res数组就是为了存储一个坐标的父亲节点，形象一些， res[x][y]= { px,py } 就代表坐标 (x,y) 的上一步是 (px,py) 。这样，我们输出时就可以从 end 一直追溯到 start 。

由于 start 先输出，我们就可从 (n,m) 开始 BFS ，让 (1,1) 作为叶子节点， (n,m) 作为根节点，这样，程序就可正序输出。

AC code：

#include<bits/stdc++.h>
#define N 200
using namespace std;
int n,m,hh,tt;
char a[N][N];
int vis[N][N];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
struct node{
    int x,y;
}q[N*N],res[N][N];
void bfs(void)
{
    q[tt++]={n,m};
    vis[n][m]=1;
    while(hh<tt)
    {
        node p=q[hh++];
        for(int i=0;i<4;i++)
        {
            int nx=p.x+dx[i];
            int ny=p.y+dy[i];
            if(nx&&ny&&nx<=n&&ny<=m&&a[nx][ny]!='*'&&!vis[nx][ny])
            {
                q[tt++]={nx,ny};
                vis[nx][ny]=1;
                res[nx][ny]={p.x,p.y};
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>a[i][j];
    }
    bfs();
    int i=1,j=1;
    while(i!=n||j!=m)
    {
        cout<<i<<' '<<j<<endl;
        node t=res[i][j];
        i=t.x;
        j=t.y;
    }
    cout<<n<<' '<<m;
    return 0;
}