C++prim 기반 미로 생 성

본 논문 의 사례 는 C+미로 생 성 을 실현 하 는 구체 적 인 코드 를 공유 하여 여러분 께 참고 하 시기 바 랍 니 다.구체 적 인 내용 은 다음 과 같 습 니 다.

c++에 있 는 vector 만 사 용 했 습 니 다.나머지 는 순수 C 와 차이 가 크 지 않 습 니 다.순수 C 는 수 동 으로 vector 를 만들어 야 할 수도 있 습 니 다.너무 번 거 로 워 서 하고 싶 지 않 습 니 다.
미궁의 일부 알고리즘 을 보 았 지만 prim 은 비교적 보기 좋 았 다.인터넷 의 코드 python c\#가 많 고 이해 하기 가 쉽 지 않 았 다.그러면 나 는 여기 서 C++(대부분의 C)로 이 목적 을 실현 했다.
prim 알고리즘:랜 덤 Prim 알고리즘 이 생 성 된 미로 의 갈림길 이 비교적 많 고 전체적으로 자 연 스 럽 고 복잡 하 며 알고리즘 의 핵심 은(위 키 백과 에 따라)이다.
1.미 로 를 벽 으로 만든다.
2.미궁의 통로 로 셀 을 선택 하고(나 는 보통 출발점 을 선택한다)옆 벽 을 목록 에 넣는다.
3.리스트 에 벽 이 있 을 때
①.목록 에서 벽 하 나 를 무 작위 로 선택 합 니 다.이 벽 에 구 분 된 두 개의 셀 이 한 개의 셀 만 접근 한 적 이 있다 면.
1).그러면 목록 에서 이 벽 을 제거 합 니 다.즉,벽 을 뚫 어 방문 하지 않 은 칸 을 미궁 의 통로 로 만 듭 니 다.
2).이 칸 의 벽 을 목록 에 추가
②.벽 양쪽 의 셀 이 모두 방문 되 었 다 면 목록 에서 이 벽 을 제거 하 십시오.
우 리 는 가장자리 목록 이 아 닌 미로 셀 의 목록 을 유지 할 수 있 습 니 다.이 미궁 셀 목록 에 접근 하지 않 은 셀 이 저장 되 어 있 습 니 다.이것 은 사 이 드 기반 버 전보 다 조금 더 많 을 것 이다.
역시 추상 적 이 니 코드 를 보 세 요.

#include <iostream>
#include <vector>
#include <cstdio>
#include <ctime>
#include <cstdlib>
using namespace std;
#define m 51//row
#define n 51//column
#define down 1
#define right 2
#define left 4
#define up 8
vector <int> block_row;
vector <int> block_column;
vector <int> block_direct;
typedef struct point
{
 int x;
 int y;
}Point;
Point start,end;
int x_num=1;
int y_num=1;
int a[m+2][n+2];
void init(){//      1=wall
 for(int i=0;i<=m+1;i++){
  for(int j=0;j<=n+1;j++){
   a[i][j]=1;//wall
  }
 }
}
void push(int x,int y,int direct){//          vector   
 block_row.push_back(x);
 block_column.push_back(y);
 block_direct.push_back(direct);
}
int count(){//             
 int cnt=0;
 if(x_num+1<=m){
  push(x_num+1,y_num,down);
  cnt++;
 } //down
 if(y_num+1<=n){
  push(x_num,y_num+1,right);
  cnt++;
 } //right
 if(x_num-1>=1){
  push(x_num-1,y_num,up);
  cnt++;
 } //up
 if(y_num-1>=1){
  push(x_num,y_num-1,left);
  cnt++;
 } //left
 return cnt;
}
int main(){
 start.x=1;//     
 start.y=1;
 end.x=m;
 end.y=n;
 init();
 srand((unsigned)time(NULL));//     
 count();
 a[1][1]=2;
 while(block_row.size()){//        （         ）    
  int num=block_row.size();
  int randnum=rand()%num;//  0-num-1      ，    vector    
  x_num=block_row[randnum];//         
  y_num=block_column[randnum];
  switch(block_direct[randnum]){//            ，                                 
   case down:{
    x_num=block_row[randnum]+1;
    y_num=block_column[randnum];
    break;
   }
   case right:{
    x_num=block_row[randnum];
    y_num=block_column[randnum]+1;
    break; 
   }
   case left:{
    x_num=block_row[randnum];
    y_num=block_column[randnum]-1;
    break;
   }
   case up:{
    x_num=block_row[randnum]-1;
    y_num=block_column[randnum];
    break;
   }
  }
  if(a[x_num][y_num]==1){//       
   a[block_row[randnum]][block_column[randnum]]=2;//   
   a[x_num][y_num]=2;//     
   count();//                   vector
  }   
  block_row.erase(block_row.begin()+randnum);//     (        ，                ，             )
  block_column.erase(block_column.begin()+randnum);
  block_direct.erase(block_direct.begin()+randnum);
 }
 for(int i=0;i<=m+1;i++){
  for(int j=0;j<=n+1;j++){
   if(a[i][j]==2){
    printf("* ");
   }
   else{
    printf("1 ");
   }
  }
  printf("
");
 }
 return 0;
}

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