MazeFinder/MazeFinder.cpp at master · wxcree/MazeFinder · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
//
// Created by 汪晓成 on 2019/10/27.
//

#include "MazeFinder.h"

void MazeFinder::MazeShow() {
    {
        for (int i=0;i<rnum;i++)
        {
            for (int j=0;j<lnum;j++)
            {
                if (maze[i][j] == 1)
                {
                    cout << "#" ;
                }
                else if (maze[i][j]==2)
                {
                    cout << "*";
                }
                else if (maze[i][j]==3)
                {
                    cout << "+";
                }
                else cout << " ";
            }
            cout << endl;
        }
    }
}

bool MazeFinder::isEnd() {
    return 1;
}

bool MazeFinder::isFork() {
    int i = 0;
    if(CanGo(x+1,y))
        i++;
    if(CanGo(x-1,y))
        i++;
    if(CanGo(x,y+1))
        i++;
    if(CanGo(x,y-1))
        i++;
    return i>1;
}

bool MazeFinder::isWall(int x, int y) {
    return maze[x][y]==1;
}

bool MazeFinder::isDone(int x, int y) {
    return maze[x][y]==2;
}

int MazeFinder::Go() {
    int result = 1;
    if(isFork()){//遇到分叉，记录分叉口位置
        forkps.push(point(x,y));
        //cout<<x<<','<<y<<endl;
        result = 3;
    }
    if(CanGo(x+1,y)){
        maze[x][y] = 2;
        x++;
    }
    else if(CanGo(x-1,y)){
        maze[x][y] = 2;
        x--;
    }
    else if(CanGo(x,y+1)){
        maze[x][y] = 2;
        y++;
    }
    else if(CanGo(x,y-1)){
        maze[x][y] = 2;
        y--;
    }
    else if(forkps.size()==0){
        maze[x][y] = 2;
        result = 0;
        cout<<"无解"<<endl;
    } else{//没地方走了，但是可以退回分叉口位置
        maze[x][y] = 2;
        x = forkps.top().x;
        y = forkps.top().y;
        forkps.pop();
        maze[x][y] = 3;
        result = 2;
    }
    maze[x][y] = 3;
    return result;
}

void MazeFinder::Find() {
    current = new stack<point>;
    current->push(point(x,y));
    while (1){
        int flag = Go();
        if(isSuccess()) {
            current->push(point(x,y));
            cout<<"ok"<<endl;
            break;
        }
        if(flag == 0)//无解
            break;
        if(flag == 1)//单纯前进一步
            current->push(point(x,y));
        else if(flag == 3){//遇到分叉路口
            //cout<<current->size()<<endl;
            map.push(*current);
            current = new stack<point>;
            current->push(point(x,y));
        } else if (flag == 2){//跳回记录位置
            current = new stack<point>;
            *current = map.top();
            map.pop();
            //cout<<"map pop"<<endl;
        }
    }
    map.push(*current);
    //cout<<x<<' '<<y<<endl;
}

bool MazeFinder::CanGo(int x, int y) {
    return !isWall(x,y)&&!isDone(x,y);
}

void MazeFinder::ShowMap() {
    while (!map.empty()){
        map.top();
        while (!map.top().empty()){
            maze[map.top().top().x][map.top().top().y] = 9;
            cout<<map.top().top().x<<","<<map.top().top().y<<endl;
            map.top().pop();
        }
        map.pop();
    }
    for (int i=0;i<rnum;i++){
        for (int j=0;j<lnum;j++){
            if (maze[i][j] == 1){
                cout << "#" ;
            }
            else if(maze[i][j]==9){
                cout<<"*";
            }
            else cout << " ";
        }
        cout << endl;
    }
}

bool MazeFinder::isSuccess() {
    return x==endx&&y==endy;
}