3kyu Path Finder #3: the Alpinist

題目背景：

Task
You are at start location [0, 0] in mountain area of NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return minimal number of climb rounds to target location [N-1, N-1]. Number of climb rounds between adjacent locations is defined as difference of location altitudes (ascending or descending).
Location altitude is defined as an integer number (0-9).

題目分析：

本道題乍一看無從下手，但是仔細分析下，題目可以這么認為：地圖中有許多格點，每個格點有一座山，山的高度從0 - 9， 從起點那座山開始，翻過n座山后，到達終點那座山，要求找一條可以使得翻上翻下的高度最矮的爬山路徑。我們可以把山與山之間的高度差抽象為各個格點的距離，那么題目就轉(zhuǎn)換為最短路徑問題，不過本道題比較卡數(shù)據(jù)，所以純粹的Dij算法是會超時的，需要加上堆優(yōu)化，算是改進版的dij算法。本質(zhì)上這道題的思路很簡單，不過dij算法碼起來比較麻煩，個人感覺記住這個模板題即可。

AC代碼：

#include <cmath> #include <queue> // solve the shortest path --> Dijkstra algorithm int V; // real nums of vertices const int NUM = 50000; // set the maximum nums of vertices is 50000 int go[4][2] = {0, 1,1, 0,0, -1,-1, 0 };struct node{ int next, c; bool operator<(const node &o) const{return c > o.c;} }; int dijkstra(std::vector<node> edge[NUM], int src) { std::priority_queue<node> Q; std::vector<int>dist(V, -1);dist[src] = 0; node tmp;tmp.next = src;tmp.c = dist[src];Q.push(tmp);while ( !Q.empty() ) { tmp = Q.top();Q.pop();int u = tmp.next;if ( u == V - 1 ) return dist[u];for (int i = 0; i < edge[u].size(); i++) {int v = edge[u][i].next;int c = edge[u][i].c;if (dist[v] == -1 || dist[u] + c < dist[v]){dist[v] = dist[u] + c; tmp.c = dist[v], tmp.next = v;Q.push(tmp);}}} return dist[V - 1]; }int path_finder(std::string maze) {int length = std::floor( std::sqrt( (double) maze.size() ) );std::cout << length << std::endl;V = length * length;std::vector<node> edge[NUM];for ( int i = 0; i < V; i++ ) edge[i].clear();for ( int x = 0; x < length; x++ ) {for ( int y = 0; y < length; y++ ) {for ( int i = 0; i < 4; i++ ) {int nx = x + go[i][0];int ny = y + go[i][1];if ( nx < 0 || nx >= length || ny < 0 || ny >= length ) continue;node tmp;tmp.next = nx * length + ny;tmp.c = std::abs(maze[nx * ( length + 1 )+ ny] - maze[x * ( length + 1 ) + y]);edge[x * length + y].push_back(tmp);}}}int src = 0;return dijkstra(edge, src); }

總結(jié)

以上是生活随笔為你收集整理的3kyu Path Finder #3: the Alpinist的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。