4kyu Path Finder #1: can you reach the exit?

題目背景：

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 true if you can reach position [N-1, N-1] or false otherwise.

Empty positions are marked .， Walls are marked W，Start and exit positions are empty in all test cases.

題目分析：

迷宮問題一般就是深搜，廣搜，最短路徑等經典的圖論問題的應用場景，這種題目在OJ中算是基本題目，刷了些題目的看到這種題目就很熟悉了。本道題我用廣搜去處理，其實廣搜的代碼很有套路，寫了幾遍就知道如何寫更舒服了，對于這種題型，其實應用場景還是蠻好分析的，難點在于正確無誤地快速碼出經典的搜索代碼。

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; };queue<Node> Q;bool 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 true;if ( nx < 0 || nx >= length || ny < 0 || ny >= length ) continue;if ( maze[nx * ( length + 1 ) + ny] == 'W' ) continue;maze[nx * ( length + 1 ) + ny] = 'W'; // make the tag, have goneNode tmp;tmp.x = nx;tmp.y = ny;Q.push(tmp);}}return false; }bool path_finder(string maze) {int length = std::floor( std::sqrt( (double) maze.size() ) );while(!Q.empty()) Q.pop();maze[0] = 'W';Node tmp;tmp.x = tmp.y = 0;Q.push(tmp);return BFS(length, maze); } 《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

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

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