题解 P2385 【青铜莲花池】

· · 题解

此题也可以用DFS

本蒟蒻写一篇DFS

思路很简单，真的非常类似跳马问题

是简单的DFS

但注意：

要写记忆化，否则TLE

还有，注意，题目说，可以向8个方向

如果只写了四个方向，就只能对2个点

注释见代码

#include<iostream>
using namespace std;
int a[100][100],f[100][100],i,j,n,m,m1,m2,x1,y1,x2,y2;
//f[i][j]记录到i行j列最少要用几步
int xd[10];
int yd[10];
inline void dfs(int x,int y,int k)//x,y坐标，k步数
{
    int i=0;
    if (a[x][y]==0||a[x][y]==2||f[x][y]<=k||x<0||y<0||x>n||y>m)
    return;
    //如果是边界，退出
   //如果x,y是石头或者水，退出
   //如果当前路径比已知路径长，退出
    f[x][y]=k;
   //否则标记为最短路径
    if (a[x][y]==4)
    return;
    //到达了终点，不用搜索了
    for (i=1;i<=8;i++)
    dfs(x+xd[i],y+yd[i],k+1);//向8个方向搜索
}
int main()
{
    cin>>n>>m>>m1>>m2;

 xd[1]=m1;xd[2]=m1;xd[3]=0-m1;xd[4]=0-m1;
 yd[5]=m1;yd[6]=m1;yd[7]=0-m1;yd[8]=0-m1;
 xd[5]=m2;xd[6]=0-m2;xd[7]=0-m2;xd[8]=m2;
 yd[1]=m2;yd[2]=0-m2;yd[3]=0-m2;yd[4]=m2;
 //设置8个方向
    for (i=1;i<=n;i++)
    for (j=1;j<=m;j++)
    {
        f[i][j]=210000000/3;
       //f初始化
    cin>>a[i][j];
    if (a[i][j]==3)
    {
        x1=i;
        y1=j;
        //寻找起点
    }
    if (a[i][j]==4)
    {
        x2=i;
        y2=j;
        //寻找终点
    }
}

    dfs(x1,y1,0);
    cout<<f[x2][y2];//最小结果存在里面了
 }

会的人请略过这一段

记忆化：用一个数组标记最短的路径，

可以节省大量的时间（以空间换时间）

（所以就不会TLE了）