4kyu Path Finder #2: shortest path

題目背景：

Task

You are at position [0, 0] in maze NxN and you can only move in one of the four cardinal directions (i.e. North, East, South, West). Return the minimal number of steps to exit position [N-1, N-1] if it is possible to reach the exit from the starting position. Otherwise, return false in JavaScript/Python and -1 in C++/C#/Java.

Empty positions are marked .. Walls are marked W. Start and exit positions are guaranteed to be empty in all test cases.

題目分析：

迷宮問題一般就是深搜，廣搜，最短路徑等經典的圖論問題的應用場景，這種題目在OJ中算是基本題目，刷了些相關題目后看到這種題目就很熟悉了。本道題我用廣搜去處理，從起點一層一層地往外剝，對于走過的格點都打上tag，每一個格點再附上到達這個格點的步數屬性，這樣廣搜到終點的話就可以獲取到步數。

AC代碼：

#include <iostream> #include <string> #include <cmath> #include <queue>using namespace std;int go[4][2] = {0, 1,0, -1,1, 0,-1, 0 };struct Node {int x, y;int steps; };queue<Node> Q;int BFS(int length, string maze) {while( !Q.empty() ) {Node now = Q.front();Q.pop();for ( int i = 0; i < 4; i++ ) {int nx = now.x + go[i][0];int ny = now.y + go[i][1];if ( nx == length - 1 && ny == length - 1 ) return ++now.steps;if ( nx < 0 || nx >= length || ny < 0 || ny >= length ) continue;if ( maze[nx * ( length + 1 ) + ny] == 'W' ) continue;maze[nx * ( length + 1 ) + ny] = 'W';Node tmp;tmp.x = nx;tmp.y = ny;tmp.steps = now.steps + 1;Q.push(tmp);}}return -1; }int path_finder(string maze) {int length = std::floor( std::sqrt( (double) maze.size() ) );if ( length == 1 ) return 0;while(!Q.empty()) Q.pop();maze[0] = 'W';Node tmp;tmp.x = tmp.y = tmp.steps = 0;Q.push(tmp);return BFS(length, maze); }

總結

以上是生活随笔為你收集整理的4kyu Path Finder #2: shortest path的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。