問題描述

給定一張迷宮地圖，該地圖標(biāo)識了迷宮各處的位置坐標(biāo)，并已知迷宮個位置的狀態(tài)信息，即該處是路還是墻，移動方向是東、南、西、北四個方向，判斷從入口是否可以到達(dá)出口

#include <iostream>using namespace std;typedef struct Node {int x;int y; } Node;/*** 創(chuàng)建 m 行 n 列的二維數(shù)組* @param m 數(shù)組行數(shù)* @param n 數(shù)組列數(shù)* @return 數(shù)組地址*/ int **createTwoDimensionalArray(int m, int n) {int **array = (int **) malloc(sizeof(int *) * m);for (int i = 0; i < m; ++i) {array[i] = (int *) malloc(sizeof(int) * n);}for (int i = 0; i < m; ++i) {for (int j = 0; j < n; j++) {array[i][j] = 0;}}return array; }/*** 給定一張 m*n 的地圖，其中 0 代表墻，其余代表路，判斷是否能從起始位置start 到達(dá)出口 end* @param map 地圖* @param start 起始位置* @param endPosition 結(jié)束位置* @param m 地圖行數(shù)* @param n 地圖列數(shù)* @return 是否能到到*/ bool canYouArrive(int **map, Node start, Node endPosition, int m, int n) {// 定義四個方向int next[4][2] = {// 向右走{0, 1},// 向左走{0, -1},// 向上走{1, 0},// 向下走{-1, 0}};// 標(biāo)記數(shù)組int **mark = createTwoDimensionalArray(m + 1, n + 1);// 遍歷隊列Node *traverseQueue = (Node *) malloc(sizeof(Node) * (m * n + 1));// 初始化隊列兩個游標(biāo)int head = 1;int tail = 1;// 將降落的起始坐標(biāo)插入隊列traverseQueue[tail++] = start;// 將降落點標(biāo)記為已遍歷mark[start.x][start.y] = 1;bool flag = false;while (head < tail) {if (flag) break;// 枚舉當(dāng)前點的四個方向for (int i = 0; i < 4; i++) {// 下一個的坐標(biāo)int x = traverseQueue[head].x + next[i][0];int y = traverseQueue[head].y + next[i][1];// 判斷是否越界if (x < 1 || x > m || y < 1 || y > n) {continue;}// 判斷是否遍歷過該點并且改點是否是陸地if (map[x][y] != 0 && mark[x][y] == 0) {// 判斷該點是否是出口if (x == endPosition.x && y == endPosition.y) {flag = true;break;}// 入隊該節(jié)點并標(biāo)記為已遍歷Node temp;temp.x = x;temp.y = y;traverseQueue[tail++] = temp;mark[x][y] = 1;}}head++;}return flag; }int main() {// 定義四個方向int next[4][2] = {// 向右走{0, 1},// 向左走{0, -1},// 向上走{1, 0},// 向下走{-1, 0}};// 地圖大小，m 行 n 列int m, n;// 輸入地圖大小cout << "輸入地圖大小:";cin >> m >> n;// 起始位置int startX, startY;// 輸入起始位置cout << "起始位置:";cin >> startX >> startY;Node start;start.x = startX;start.y = startY;// 結(jié)束位置int endX, endY;cout << "結(jié)束位置:";cin >> endX >> endY;Node endPosition;endPosition.x = endX;endPosition.y = endY;// 加載地圖// ① m 行 n 列的數(shù)組int **map = createTwoDimensionalArray(m + 1, n + 1);// ② 創(chuàng)建地圖int num;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {cin >> num;map[i][j] = num;}}bool flag = canYouArrive(map, start, endPosition, m, n);if (flag)cout << "true" << endl;else cout << "false" << endl;return 0; }

測試數(shù)據(jù)

輸入地圖大小:10 10 起始位置:6 8 結(jié)束位置:4 6 1 2 1 0 0 0 0 0 2 3 3 0 2 0 1 2 1 0 1 2 4 0 1 0 1 2 3 2 0 1 3 2 0 0 0 1 2 4 0 0 0 0 0 0 0 0 1 5 3 0 0 1 2 1 0 1 5 4 3 0 0 1 2 3 1 3 6 2 1 0 0 0 3 4 8 9 7 5 0 0 0 0 0 3 7 8 6 0 1 2 0 0 0 0 0 0 0 0 1 0

測試結(jié)果

輸入地圖大小:10 10 起始位置:6 8 結(jié)束位置:4 6 1 2 1 0 0 0 0 0 2 3 3 0 2 0 1 2 1 0 1 2 4 0 1 0 1 2 3 2 0 1 3 2 0 0 0 1 2 4 0 0 0 0 0 0 0 0 1 5 3 0 0 1 2 1 0 1 5 4 3 0 0 1 2 3 1 3 6 2 1 0 0 0 3 4 8 9 7 5 0 0 0 0 0 3 7 8 6 0 1 2 0 0 0 0 0 0 0 0 1 0 true

超強(qiáng)干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的迷宫可达的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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