北京家居网站建设,金沙网站怎么做代理,抗疫物资捐赠网,精灵网站建设问题 D: 共享单车
题目描述
共享单车走进烟台#xff0c;小明决定尝试。小明启动共享单车 App#xff0c;轻松地找到附近的单车。那么问题来了#xff0c;到最近的那辆单车#xff0c;小明大约要走多少米呢#xff1f;
现在简化问题。将地图设定成一个由 100100 米的像…问题 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(n1 || n2) 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?spm1001.2014.3001.5501
思路
从o点出发要寻找距离最近的共享单车因为要求最近距离我们初始化距离为无穷远用一个d数组来记录个点距离o点的最短距离并初始化为无穷大每次进行下一次dfs之前首先先进行判断走这一步是否可以使到达我们要到达的点的距离更近这样进入dfs便可以直接更新找到一个共享单车做比较寻找最优解。
代码实现
#includeiostream
#includecstring
#includequeue
#includevector
#includealgorithmusing namespace std;typedef long long ll;typedef pairint,int PII;const int INF0x3f3f3f3f;
const int N105;char g[N][N];
bool vis[N][N];int ansINF;
bool ffalse;
int n,m;int d[N][N];///记忆化搜索int xx,yy;void dfs(int x,int y,int dis)///(x,y)记录点的位置dis记录该点距离o点的距离
{if(x1 || xn || y1 || ym) return;///判断点是否越界d[x][y]dis; /// 更新最短距离因为已经做过判断了所以这里直接更新if(g[x][y]x)///找到共享单车{ftrue;ansmin(ans,d[x][y]);///选择距离更近的最优解return;}else{if(!vis[x1][y] dis100d[x1][y] g[x1][y]!*) ///右{vis[x1][y]true;dfs(x1,y,dis100);vis[x1][y]false;}if(!vis[x-1][y] dis100d[x-1][y] g[x-1][y]!*) ///左{vis[x-1][y]true;dfs(x-1,y,dis100);vis[x-1][y]false;}if(!vis[x][y1] dis100d[x][y1] g[x][y1]!*) ///上{vis[x][y1]true;dfs(x,y1,dis100);vis[x][y1]false;}if(!vis[x][y-1] dis100d[x][y-1] g[x][y-1]!*) ///下{vis[x][y-1]true;dfs(x,y-1,dis100);vis[x][y-1]false;}if(!vis[x-1][y-1] dis141d[x-1][y-1] g[x-1][y-1]!*) ///左下{vis[x-1][y-1]true;dfs(x-1,y-1,dis141);vis[x-1][y-1]false;}if(!vis[x1][y1] dis141d[x1][y1] g[x1][y1]!*) ///右上{vis[x1][y1]true;dfs(x1,y1,dis141);vis[x1][y1]false;}if(!vis[x-1][y1] dis141d[x-1][y1] g[x-1][y1]!*) ///左上{vis[x-1][y1]true;dfs(x-1,y1,dis141);vis[x-1][y1]false;}if(!vis[x1][y-1] dis141d[x1][y-1] g[x1][y-1]!*) ///右下{vis[x1][y-1]true;dfs(x1,y-1,dis141);vis[x1][y-1]false;}}return;
}void solve()
{cinnm;ansINF;///初始化memset(d,0x3f,sizeof(d)); ///初始化图上每个点到小明的距离为无穷远ffalse;///不能到达共享单车memset(vis,false,sizeof(vis));///因为是多组数据输入输出因此要初始化for(int i1; in; i)///图的存储{for(int j1; jm; j){cing[i][j];if(g[i][j]o){xxi;yyj;}}}dfs(xx,yy,0);///从o点开始搜索if(ffalse) printf(-1\n);else coutansendl;}int main()
{int T;cinT;while(T--){solve();}return 0;
}
