溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
本文實例為大家分享了C++實現(xiàn)走迷宮的具體代碼，供大家參考，具體內(nèi)容如下
用n*n個小方格代表迷宮，每個方格上有一個字符0或1，0代表這個格子不能走，1代表這個格子可以走。只能一個格子一個走，而且只能從一個格子向它的上、下、左、右四個方向走，且不能重復(fù)。迷宮的入口和出口分別位于左上角和右下角，存在唯一的一條路徑能夠從入口到達出口，試著找出這條路徑。
例如，下圖是一個迷宮，紅色表示走出迷宮的一條路徑
輸入：入口坐標（startX，startY）,出口坐標（endX，endY）
輸出：如果存在這樣一條路徑，則輸出1，并輸出路徑(0,0)->(1,0)->(1,1)->(2,1)->(2,2)->(3,2)->(4,2)->(5,2)->(5,3)->(5,4)->(5,5)->(4,5)->(4,6)->(4,7)->(5,7)->(6,7)->(7,7)
思路：利用回溯法求解。
首先，根據(jù)輸入在矩陣中找到路徑的起點。假設(shè)矩陣中某個格子的字符為1，就往相鄰的格子尋找字符為1的格子。除了在矩陣邊界上的格子之外，每個格子都有4個相鄰的格子。重復(fù)這個過程直到在矩陣中找到相應(yīng)的出口位置。
當在矩陣中定位了路徑上n個格子的位置后，在與第n個格子周圍都沒有找到第n+1個格子為1，則只好在路徑上回到第n-1個格子，重新去尋找第n個字符為1的格子
由于路徑不能重復(fù)進入格子，我們需要定義一個字符矩陣一樣大小的布爾值矩陣，用來標記路徑是否已經(jīng)進入了相應(yīng)格子。
代碼實現(xiàn)如下
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, int startX,int startY, int endX, int endY,vector<int>& Path)
{
if (matrix == NULL || rows < 1 || cols < 1 || startX<0||startY<0||endX<0||endY<0||(startX==endX&&startY==endY))
return false;
bool* visited = new bool[rows*cols]; //定義一個輔助矩陣，用來標記路徑是否已經(jīng)進入了每個格子
memset(visited, 0, rows*cols);
int pathLength = 0;
if (hasPathCore(matrix, rows, cols, startX, startY, endX, endY, visited, Path))
{
return true;
}
delete[] visited;
return false;
}
/*此函數(shù)用來判斷在當前路徑滿足條件下，相鄰格子中是否存在一個格子滿足條件*/
bool hasPathCore(char* matrix, int rows, int cols, int row, int col, int endX, int endY, bool* visited, vector<int>& Path)
{
if ((row == endX) && (col == endY)&&(matrix[row*cols+col]=='1'))
{
Path.push_back(endY);
Path.push_back(endX);
return true;
}
bool hasPath = false;
if (row >= 0 && row < rows&&col >= 0 && col < cols&&matrix[row*cols + col] == '1' && !visited[row*cols + col])
{
// ++pathLength;
visited[row*cols + col] = true;
Path.push_back(col);
Path.push_back(row);
/*如果矩陣格子(row,col)字符為1時，從它的4個相鄰格子中尋找下一個字符為1的格子*/
hasPath = hasPathCore(matrix, rows, cols, row, col - 1, endX, endY, visited,Path) ||
hasPathCore(matrix, rows, cols, row - 1, col, endX, endY, visited,Path) ||
hasPathCore(matrix, rows, cols, row, col + 1, endX, endY, visited,Path) ||
hasPathCore(matrix, rows, cols, row + 1, col, endX, endY, visited,Path);
if (!hasPath) //如果沒找到，則說明當前第n個格子定位不正確，返回上一個位置重新定位
{
visited[row*cols + col] = false;
Path.pop_back();
Path.pop_back();
}
}
return hasPath;
}
};
int main()
{
// char* matrix = "abcesfcsadee";
char* matrix = "1000000110110001101000010111011110100000010000001"; //設(shè)置迷宮
int startX, startY, endX, endY;
cin >> startX >> startY >> endX >> endY; //輸入起始結(jié)束坐標
Solution s;
vector<int> Path;
bool re = s.hasPath(matrix, 7, 7, startX,startY,endX,endY,Path);
cout << re << endl;
for (int i = 0; i < Path.size();)
cout << "(" << Path[i++] << ',' << Path[i++] << ")" << " ";
cout << endl;
return 0;
}
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼