C++간단 한 미로 코드 구현

본 논문 의 사례 는 C+미로 로 가 는 구체 적 인 코드 를 공유 하여 여러분 께 참고 하 시기 바 랍 니 다.구체 적 인 내용 은 다음 과 같 습 니 다.
n*n 개의 작은 격자 로 미 로 를 대표 합 니 다.각 격자 에 0 또는 1,0 은 이 격자 가 갈 수 없다 는 것 을 의미 합 니 다.1 은 이 격자 가 갈 수 있다 는 것 을 의미 합 니 다.한 칸 만 갈 수 있 고 한 칸 에서 위,아래,왼쪽,오른쪽 네 방향 으로 만 갈 수 있 으 며 중복 할 수 없다.미궁의 입구 와 출구 는 각각 왼쪽 상단 과 오른쪽 하단 에 위치 하고 입구 에서 출구 에 도착 할 수 있 는 유일한 경로 가 존재 하 므 로 이 경 로 를 찾 아 보 세 요.
예 를 들 어 아래 그림 은 미로 이 고 빨간색 은 미 로 를 벗 어 나 는 경 로 를 나타 낸다.

입력:입구 좌표(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,5)->(4,6)->(4,7)->(7,7)
사고방식:역 추적 법 을 이용 하여 해답 을 구한다.
우선,입력 에 따라 행렬 에서 경로 의 출발점 을 찾 습 니 다.행렬 의 한 칸 의 문자 가 1 이 라 고 가정 하면 인접 한 칸 으로 문자 가 1 인 칸 을 찾 습 니 다.행렬 경계 에 있 는 칸 을 제외 하고 칸 마다 4 개의 인접 한 칸 이 있다.행렬 에서 해당 하 는 출구 위 치 를 찾 을 때 까지 이 과정 을 반복 합 니 다.
행렬 에서 경로 의 n 칸 위 치 를 찾 은 후에 n 칸 주위 에서 n+1 칸 을 1 로 찾 지 못 하면 경로 에서 n-1 칸 으로 돌아 가 n 번 째 문자 가 1 인 칸 을 다시 찾 을 수 밖 에 없다.
경로 가 격자 에 중복 되 지 않 기 때문에 우 리 는 문자 행렬 과 같은 크기 의 불 값 행렬 을 정의 하여 경로 가 해당 격자 에 들 어 갔 는 지 여 부 를 표시 해 야 합 니 다.
코드 구현 은 다음 과 같 습 니 다.

#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];    //        ，                 
 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;
 }
 
 /*                 ，                 */
 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";  //    
 int startX, startY, endX, endY;
 cin >> startX >> startY >> endX >> endY;         //        
 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;
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.