미궁 문제 [데이터 구조 실험 보고서]

데이터 구조 실험 보고서
실험 명칭: 실험 2 미궁 문제
학 번: * * *
이름: gnosed
시험 날짜: 2017.10.23
 
실험 목적
1. 역 추적 법 이 미로 문 제 를 해결 하 는 데 사용 되 는 응용 을 이해한다.
2. 창고 의 사용 을 파악
 
2. 실험의 구체 적 인 내용
1. 실험 문제 1:
(1) 제목
역 추적 법 으로 미궁 문 제 를 풀 면 한 창고 로 탐색 의 서열 을 보존 할 수 있다.또한 이 미로 의 걷 기 에서 한 점 에 서 있 으 면 8 가지 방향 으로 선택 할 수 있다.
미로
Enter-> 0   1   1  1   0   0  0   0   0   0
              0   0  0   1   0  0   0   1  0   0
              0   1  0   1   1  0   0   1  0   0
              0   1  0   0   1  0   1   1  0   0
              0   1  0   0   1  0   1   1  0   0
              1   1  1   0   1  0   1   0  0   0
              0   0  1   0   0  0   1   0  1   1
              0   0  1   0   0  0   1   0  1   1
              0   1  1   0   1  0   1   0  0   0
              0   0  0   0   1  0   1   1  0   0 --> EXIT
다음은 가능 한 경로 입 니 다. (주의: 입구 에서 출구 까지 여러 가지 경로 가 있 을 수 있 습 니 다. 우선 선택 하 는 방향 이 다 르 고 경로 도 다 를 수 있 습 니 다!)
 Path: ( maze[0][0], maze[1][0],maze[1][1], maze[1][2], maze[2][2],
          maze[3][2], maze[3][3], maze[4][3],maze[5][3], maze[6][3],
          maze[6][4], maze[6][5], maze[5][5],maze[4][5], maze[3][5],
          maze[2][5], maze[2][6], maze[1][6],maze[0][6], maze[0][7],
          maze[0][8], maze[1][8], maze[2][8],maze[3][8], maze[4][8],
          maze[5][8], maze[5][7], maze[6][7],maze[7][7], maze[8][7],
          maze[8][8], maze[8][9], maze[9][9])
 
Enter-> X   1   1  1   0   0  X---X---X   0
              X---X---X   1  0   0   X  1   X   0
              0   1  X   1   1  X---X   1   X   0
              0   1  X---X   1   X  1   1   X   0
              0   1  0   X   1  X   1   1  X   0
              1   1  1   X   1  X   1   X---X  0
              0   0  1   X---X---X   1  X   1   1
              0   0   1  0   0   0   1   X  1   1
              0   1  1   0   1  0   1   X-- X-- X
              0   0  0   0   1  0   1   1  0   X --> EXIT
 
(2) 분석
규정:
1）  미궁 왼쪽 상단 의 첫 번 째 위 치 는 입구 이 고 오른쪽 하단 의 첫 번 째 위 치 는 출구 입 니 다.
2）  탐색 의 방향 은 위 에서 시계 방향 으로 회전 하고 상하 좌우 네 방향 이다.
3）  입력: m, n, m * n 개의 미로 상태, 0 은 통 로 를 표시 하고 1 은 벽 이 있 음 을 표시 합 니 다.
4）  출력: 미로 로 통 하 는 경 로 를 찾 으 면 출력 경로 의 각 단계 의 위 치 를 찾 습 니 다.그렇지 않 으 면 힌트 를 찾 을 수 없습니다.
 
데이터 구조:
1）  2 차원 배열 MAZE [m] [n] 로 미궁의 상 태 를 나타 내 고 0 은 통 로 를 나타 내 며 1 은 벽 이 있 음 을 나타 내 고 2 는 이미 지나 갔다 는 것 을 나타 낸다.
2）  STL 의 스 택 으로 지나 간 경 로 를 저장 하고 스 택 을 누 르 면 다음 단계 에 들 어 가 는 것 을 표시 하 며 스 택 을 반품 하면 이전 단계 로 돌아 가 는 것 을 표시 합 니 다.모든 스 택 요 소 는 현재 위치 좌표 입 니 다.
 
알고리즘 프로 세 스:
입구 위치 부터 창고 에 넣 으 세 요.
1) 스 택 상단 요소 값 (스 택 에서 나 오지 않 음) 을 가 져 옵 니 다.
2) 정 해진 방향 으로 다음 단계 의 위 치 를 판단 한다. 즉, 원래 걸 어 온 방향 을 제외 하고 나머지 세 방향 에 통로 가 있 는 지 판단 한다.
3) 하나 (첫 번 째 위치 가 지나 간 경우 다음) 통로 의 위 치 를 판단 하여 창고 에 넣는다.
4) 세 방향 이 모두 벽 이면 창고 에서 나온다.
5) 출구 가 발견 되면 수출 경로.창고 가 비어 있 으 면 노선 이 없 음 을 알려 줍 니 다.출구 가 발견 되 지 않 고 창고 가 비어 있 지 않 으 면 1) 2) 3) 4 를 반복 합 니 다.
 
(3) 실험 코드
원본 코드:
 

#include 
#include 

using namespace std;

const int maxm=100,maxn=100;
int MAZE[maxm][maxn],m,n;
struct pos{
    int i,j;
};
void create(){
    for(int i=0;i>t;
        MAZE[i][j]=t;
    }
}
struct pos Move(struct pos curr){
    /*       ，        ，        
        ：
            
                 */
    struct pos next=curr;
    int x=curr.i,y=curr.j;
    //  
    if(!MAZE[x-1][y]&&(x-1)>=0&&
       MAZE[x-1][y]!=2){
           next.i=x-1;//  x    
           MAZE[x-1][y]=2;//      
        return next;//         
    }//  
    else if(!MAZE[x][y+1]&&(y+1)=0&&
            MAZE[x][y-1]!=2){
                next.j=y-1;
                MAZE[x][y-1]=2;
        return next;
    }
    return curr;//  ，       
}
void findPath(){
    stack Path;
    struct pos curr,nex;
    curr.i=0;curr.j=0;
    Path.push(curr);//    
    MAZE[0][0]=2;//     
    while(!Path.empty()){//5)
        curr=Path.top();//1)
//        cout<=0;k--){
                cout<";
            }
            return ;
        }
    }
    cout<>m>>n;
    create();
    findPath();
    return 0;
}

 
 
 
 
테스트 데이터:
Input
 

10  10
0   1  1   1   0  0   0   0  0   0
0   0  0   1   0  0   0   1  0   0
0   1  0   1   1  0   0   1  0   0
0   1  0   0   1  0   1   1  0   0
0   1  0   0   1  0   1   1   0   0
1   1  1   0   1  0   1   0  0   0
0   0  1   0   0  0   1   0  1   1
0   0  1   0   0  0   1   0  1   1
0   1  1   0   1  0   1   0  0   0
0   0  0   0   1  0   1   1  0   0

 
 
 
Coutput
 

(0,0)->(1,0)->(1,1)->(1,2)->(2,2)
->(3,2)->(3,3)->(4,3)->(5,3)->(6,3)
->(6,4)->(6,5)->(5,5)->(4,5)->(3,5)
->(2,5)->(1,5)->(0,5)->(0,6)->(0,7)
->(0,8)->(0,9)->(1,9)->(2,9)->(3,9)
->(4,9)->(5,9)->(5,8)->(5,7)->(6,7)
->(7,7)->(8,7)->(8,8)->(8,9)->(9,9)

 
 
 
Input
 

10  10
0   1  1   1   0  0   0   0  0   0
0   0  0   1   0  0   0   1  0   0
0   1  0   1   1  0   0   1  0   0
0   1  0   0   1  0   1   1  0   0
0   1  0   0   1  0   1   1   0   0
1   1  1   0   1  0   1   0  0   0
0   0  1   0   1  0   1   0  1   1
0   0  1   0   1  0   1   0  1   1
0   1  1   0   1  0   1   0  0   0
0   0  0   0   1  0   1   1  0   0

 
Coutput
 

NO Path!

 
 
 
3. 실험 소결
 
4. 567917. 먼저 코드 를 실현 하기 전에 문 제 를 분석 하고 알고리즘 을 디자인 하 며 문 서 를 작성 하 는 것 은 자신의 큰 발전 이 라 고 할 수 있다. 
4. 567917. 자신의 생각 을 실현 하 는 것 은 선생님 이 제공 하 는 방법 에 국한 되 지 않 는 다.예 를 들 어 이 실험 에서 저 는 미궁 의 '벽' 을 추가 하지 않 았 습 니 다. 탐색 할 때 경계 판단 에 주의 하면 공간 을 절약 할 수 있 습 니 다
4. 567917. 부족 한 점 은 처음에 문 제 를 결합 하여 스 택 요소 의 구 조 를 고려 할 때 뚜렷 하지 않 아서 디자인 알고리즘 이 없 었 다 는 것 이다
4. 567917. 이 실험의 가장 큰 교훈 은 원래 두 개의 지향 구조 체 의 지침 을 통 해 이 두 구조 체 가 같 는 지 여 부 를 판단 하 는 것 이다.사실 저 는 당연히 구조 체 의 값 이 같다 고 판단 하고 싶 지만 함수 에서 돌아 온 것 은 지침, 즉 주소 이 고 두 구조 체 가 같다 고 직접 판단 할 수 없 기 때문에 지침 을 통 해 두 구조 체 가 같다 고 판단 하지 못 해서 이 bug 는 깊이 숨 어 있 습 니 다.사고방식 을 바 꾸 고 그 정의 에서 출발 하여 두 구조 체 가 같다 고 직접적 으로 판단 할 수 없 는 이상 구조 체 안의 모든 요소 유형 이 같다 고 판단 한다