先上題目
光明小學的小朋友們要舉行一年一度的接力跑大賽了，但是小朋友們卻遇到了一個難題：設計接力跑大賽的線路，你能幫助他們完成這項工作么？
光明小學可以抽象成一張有N個節(jié)點的圖，每兩點間都有一條道路相連。光明小學的每個班都有M個學生，所以你要為他們設計出一條恰好經過M條邊的路徑。
光明小學的小朋友們希望全盤考慮所有的因素，所以你需要把任意兩點間經過M條邊的最短路徑的距離輸出出來以供參考。你需要設計這樣一個函數：
res[][] Solve( N, M, map[][]);
注意：map必然是N * N的二維數組，且map[i][j] == map[j][i]，map[i][i] == 0，-1e8 <= map[i][j] <= 1e8。（道路全部是無向邊，無自環(huán)）2 <= N <= 100, 2 <= M <= 1e6。map數組表示了一張稠密圖，其中任意兩個不同節(jié)點i,j間都有一條邊，邊的長度為map[i][j]。N表示其中的節(jié)點數。
你要返回的數組也必然是一個N * N的二維數組，表示從i出發(fā)走到j，經過M條邊的最短路徑
你的路徑中應考慮包含重復邊的情況。樣例：
N = 3
M = 2
map = {
{0, 2, 3},
{2, 0, 1},
{3, 1, 0}
}輸出結果result為：
result = {
{4, 4, 3},
{4, 2, 5},
{3, 5, 2}
}輸入樣例：
3
2
3 3
0 2 3
2 0 1
3 1 0輸出樣例：
[[4, 4, 3],
[4, 2, 5],
[3, 5, 2]]
題目分析
首先確定的就是，題目給出的是一個有N個節(jié)點的無向完全圖，同時，要求只能走M步，也就是搜索長度被確定為了M，那這樣其實思路就很清晰了。由于只給了30分鐘，那么太精巧的算法估計一時半會想不出來（對于我這種菜鳥來說啊哈哈哈哈或）那么怎么辦？當然是暴力解法最有用了。通過遞歸的方法，在有限的步長下遍歷所有的可能，然后返回最小距離即可。十分感謝CSDN的大佬@蛋烘糕（https://blog.csdn.net/u012465304/article/details/81180707）提供的思路，他的代碼是C語言的，如果大家對C比較熟悉可以參考他的代碼。
代碼思路
這里就是一個比較頭疼的地方了，如果是遞歸遍歷，那么參數需要的東西就很多了，包括步長，距離等，同時，對于每一個點在搜索完后的回退，要記得同樣要給步長減一，不過如果你的參數形式是這樣的，比如len是步長dis是距離，參數是len + 1和dis + graph[new_start][dest]，這樣的話，由于這樣的傳參方式不會改變變量本身大小，那么就直接用就好，不需要再回退的時候還要重新計算，算是一個小技巧。
實際我用了好多好多參數，但是用上的不多，測試結束后回看自己的代碼，怕是會把HR氣死
部分代碼
欸，為了讓大家也有鍛煉的機會，我這里就提供深度遍歷部分的Python代碼，其他部分大家就可以參考這段代碼依次類推啦，但是不瞞大家，我花時間最多的地方除了理解題目和思路，就是在如何按照格式輸入的問題了……真是沒想到：
def dfs(graph, dest, curr, step, M, N, min_dis, dis):
if step == M:
if curr == dest:
if min_dis > dis:
min_dis = dis
return min_dis
for i in range(N):
if i is not curr:
min_dis = dfs(graph, dest, i, step + 1, M, N, min_dis, dis + int(graph[curr][i]))
return min_dis
反思
現在也是校招旺季，我也參加了不少的編程線上測試，不得不說自己真的是菜得可怕，尤其是在Google的CodeJam上，自己絞盡腦汁好不容易拿下第一題的時候，看排行榜已經有人快做完了。
？？？？？
果然是大佬們啊，所以說其實寫代碼這個東西尤其是線上測試，我覺得就是要多練，很多的東西我覺著其實是有一些套路的，同時，比如做多了以后，手自然熟悉，不會一上手，大部分時間都花在了回憶基本操作上。尤其是在時間有限的情況下更為忌諱。當然哈哈哈，想要成為那些Google的大佬們還是需要很多時間的訓練，同時再加上一點點天賦加成，應該也是可以無限接近的，加油加油！
