問題 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;
}
)
