YTU 3166 共享单车 DFS 记忆化搜索

问题 D: 共享单车

题目描述

共享单车走进烟台，小明决定尝试。小明启动共享单车 App，轻松地找到附近的单车。那么问题来了，到最近的那辆单车，小明大约要走多少米呢？

现在简化问题。将地图设定成一个由 100×100 米的像素块组成的二维平面区域。如果一个方块内有单车，则像素块显示为字符 x；如果此方块内是可以通行的路，则显示为 .；再如果方块是建筑物，则显示为 *，建筑物不能通行。

小明在地图上的位置显示为 o，可以朝，“上”、“下”、“左”，“右”，“左上”，“左下”，“右上”，“右下”八个方向走。下图所示为一个小明站在像素方块 O，如果小明向右走到 X，则走 100 米；如果向右上走，则走 141 米（不需要开方）。

假设小明和单车都在方块的中央。现在给出 T 幅根据以上规则建立的地图，地图行数和列数分别为 n 和 m，请分别估算小明要走多少米才能到最近的单车？

给出的地图中至少有一辆单车，如果最终无法到达单车的位置，输出 -1。

输入

第 1 行 T，表示下面有 T 组测试数据

对于每组测试数据

第 1 行 n 和 m，表示地图的大小；

第 2 行开始，给出具体的地图 。

输出

T 行数据

每行 1 个整数，表示问题的解

输入输出样例

样例输入 #1

复制

2
3 8
.....x..
.o...x..
........
8 10
.***......
.***......
.***..x...
..........
.....*****
..o..*****
.......x..
...*******

样例输出 #1

复制

400
523

提示

如果计算中出现小数，那么直接舍弃。最后的输出的结果为整型。

记忆化搜索：

记忆化搜索是深搜的一种剪枝策略，记忆化搜索就是让程序记住一些东西，然后在需要时可以快速调用，用什么来存贮数据？用数组

记忆化搜索是在搜索过程中，会有很多重复计算,如果我们能记录一些状态的答案，就可以减少复搜索量
 

记忆化搜索的核心实现:

1.首先，要通过一个数组记录已经存储下的搜索结果

2.状态表示，由于是要用数组实现，所以状态最好可以用数字表示，

3.在每一状态搜索的开始，高效的使用数组查看这个状态是否出现过，如果已经做过，直接调用答案，如果没有，则按正常方法搜索

以斐波那契数列为例，记忆化代码入下：

int memorize[N]; //保存结果
int fib(int n)
{if(n==1 || n==2) return 1; if(memorize[n]!=0) return memorize[n];  //直接返回保存的结果，不再递归memorize[n]=fib(n-1)+fib(n-2);          //递归计算结果，并记忆return memorize[n];
}

在这段代码中，一个斐波那契数列只计算一次，所以总时间复杂度为O(n)
 

我们先用一道熟悉的题目引入记忆化搜索：
https://blog.csdn.net/2302_79545206/article/details/137286031?spm=1001.2014.3001.5501

思路： 

从o点出发，要寻找距离最近的共享单车，因为要求最近距离，我们初始化距离为无穷远，用一个d数组来记录个点距离o点的最短距离，并初始化为无穷大，每次进行下一次dfs之前，首先先进行判断走这一步是否可以使到达我们要到达的点的距离更近，这样进入dfs便可以直接更新，找到一个共享单车，做比较寻找最优解。

代码实现： 

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>using namespace std;typedef long long ll;typedef pair<int,int> PII;const int INF=0x3f3f3f3f;
const int N=105;char g[N][N];
bool vis[N][N];int ans=INF;
bool f=false;
int n,m;int d[N][N];///记忆化搜索int xx,yy;void dfs(int x,int y,int dis)///(x,y)记录点的位置，dis记录该点距离o点的距离
{if(x<1 || x>n || y<1 || y>m) return;///判断点是否越界d[x][y]=dis; /// 更新最短距离，因为已经做过判断了，所以这里直接更新if(g[x][y]=='x')///找到共享单车{f=true;ans=min(ans,d[x][y]);///选择距离更近的最优解return;}else{if(!vis[x+1][y] && dis+100<d[x+1][y] && g[x+1][y]!='*') ///右{vis[x+1][y]=true;dfs(x+1,y,dis+100);vis[x+1][y]=false;}if(!vis[x-1][y] && dis+100<d[x-1][y] && g[x-1][y]!='*') ///左{vis[x-1][y]=true;dfs(x-1,y,dis+100);vis[x-1][y]=false;}if(!vis[x][y+1] && dis+100<d[x][y+1] && g[x][y+1]!='*') ///上{vis[x][y+1]=true;dfs(x,y+1,dis+100);vis[x][y+1]=false;}if(!vis[x][y-1] && dis+100<d[x][y-1] && g[x][y-1]!='*') ///下{vis[x][y-1]=true;dfs(x,y-1,dis+100);vis[x][y-1]=false;}if(!vis[x-1][y-1] && dis+141<d[x-1][y-1] && g[x-1][y-1]!='*') ///左下{vis[x-1][y-1]=true;dfs(x-1,y-1,dis+141);vis[x-1][y-1]=false;}if(!vis[x+1][y+1] && dis+141<d[x+1][y+1] && g[x+1][y+1]!='*') ///右上{vis[x+1][y+1]=true;dfs(x+1,y+1,dis+141);vis[x+1][y+1]=false;}if(!vis[x-1][y+1] && dis+141<d[x-1][y+1] && g[x-1][y+1]!='*') ///左上{vis[x-1][y+1]=true;dfs(x-1,y+1,dis+141);vis[x-1][y+1]=false;}if(!vis[x+1][y-1] && dis+141<d[x+1][y-1] && g[x+1][y-1]!='*') ///右下{vis[x+1][y-1]=true;dfs(x+1,y-1,dis+141);vis[x+1][y-1]=false;}}return;
}void solve()
{cin>>n>>m;ans=INF;///初始化memset(d,0x3f,sizeof(d)); ///初始化图上每个点到小明的距离为无穷远f=false;///不能到达共享单车memset(vis,false,sizeof(vis));///因为是多组数据输入输出因此要初始化for(int i=1; i<=n; i++)///图的存储{for(int j=1; j<=m; j++){cin>>g[i][j];if(g[i][j]=='o'){xx=i;yy=j;}}}dfs(xx,yy,0);///从o点开始搜索if(f==false) printf("-1\n");else cout<<ans<<endl;}int main()
{int T;cin>>T;while(T--){solve();}return 0;
}