// ConsoleApplication12.cpp : 定义控制台应用程序的入口点。
//
#include “stdafx.h”
#include #include #include #include #include #include #define MAXSIZE 5000
using namespace std;
struct point {
int x;
int y;
point(int x0 = 0, int y0 = 0):x(x0),y(y0) {}
point(point& p) {
this->x = p.x;
this->y = p.y;
}
bool operator==(point& p){
return this->x == p.x&&this->y == p.y;
}
bool operator!=(point& p) {
return !(this == p);
}
};
int direction[8][2] = { { 1,1 },{ 1,-1 },{ -1,1 },{ -1,-1 } ,{1,0},{0,1},{-1,0},{0,-1}};
struct stkpoint {
point p;
int dir;
stkpoint(point poi = NULL) :p(poi), dir(0) {};
bool operator==(stkpoint&q){
return (this->p) == (q.p);
}
};
templateclass pointStack {
T vendor;
int top;
public:
pointStack() {
vendor = new T[MAXSIZE];
top = -1;
}
void push(T p) {
vendor[++top] = p;
}
T pop() {
if (top == -1) { cout << “empty”; exit(0); }
return vendor[top–];
}
point operator[](int index) {
return T[index];
}
bool IsIn(T q) {
for (int i = 0; i <= top; i++) {
if (vendor[i] == q) {
return true;
}
}
return false;
}
int getTop() {
return top;
}
};
class puzzle {
int** puz;
//pointStack path;
int length;
protected:
void opendoor(int x1, int y1, int x2, int y2) {
if (puz[length - 1][length - 1] == 1)puz[length - 1][length - 1] = 0;
if (x1 == x2) {
int pos = y1 + rand() % ((y2 - y1) / 2 + 1) 2;
if (pos >= length)pos–;
puz[x1][pos] = 0;
}
else if (y1 == y2) {
int pos = x1 + rand() % ((x2 - x1) / 2 + 1) 2;
if (pos >= length)pos–;
puz[pos][y1] = 0;
}
else {
cout << “error!” << endl;
exit(0);
}
//cout << “opened” << endl;
}
void formpuzzle(int x, int y, int height, int width, bool ans) {
if (ans) {
print(2);
system(“cls”);
}
int xpos, ypos;
if (height <= 2 || width <= 2)
{
//cout << “finished one step” << endl;
return;
}
xpos = x + rand() % ((height) / 2) 2 + 1;
for (int i = y; i < y + width; i++) {
puz[xpos][i] = 1;
}
ypos = y + rand() % ((width) / 2) * 2 + 1;
for (int i = x; i < x + height; i++) {
puz[i][ypos] = true;
}
int isClosed = rand() % 4 + 1;
switch (isClosed)
{
case 1:
opendoor(xpos + 1, ypos, x + height - 1, ypos);// 2
opendoor(xpos, ypos + 1, xpos, y + width - 1);// 3
opendoor(x, ypos, xpos - 1, ypos);// 4
break;
case 2:
opendoor(xpos, ypos + 1, xpos, y + width - 1);// 3
opendoor(x, ypos, xpos - 1, ypos);// 4
opendoor(xpos, y, xpos, ypos - 1);// 1
break;
case 3:
opendoor(x, ypos, xpos - 1, ypos);// 4
opendoor(xpos, y, xpos, ypos - 1);// 1
opendoor(xpos + 1, ypos, x + height - 1, ypos);// 2
break;
case 4:
opendoor(xpos, y, xpos, ypos - 1);// 1
opendoor(xpos + 1, ypos, x + height - 1, ypos);// 2
opendoor(xpos, ypos + 1, xpos, y + width - 1);// 3
break;
default:
break;
}
// 左上角
formpuzzle(x, y, xpos - x, ypos - y, ans);
// 右上角
formpuzzle(x, ypos + 1, xpos - x, width - ypos + y - 1, ans);
// 左下角
formpuzzle(xpos + 1, y, height - xpos + x - 1, ypos - y, ans);
// 右下角
formpuzzle(xpos + 1, ypos + 1, height - xpos + x - 1, width - ypos + y - 1, ans);
}
bool go(int x, int y, bool ans) {//递归算法
if (ans) { print(); system("cls"); };
if (puz\[x\]\[y\] != 0)return false;
point *p = new point(x, y);
//if (!path.IsIn(\*p))path.push(\*p);
puz\[x\]\[y\] = 2;
if (x == length - 1 && y == length - 1) { return true; }
if (x < length - 1)
if (puz\[x+1\]\[y\]!=2 && go(x + 1, y, ans))
return true;
if (y < length - 1)
if (puz\[x\]\[y+1\]!=2 && go(x, y + 1, ans))
return true;
if (x > 0)
if (puz\[x-1\]\[y\]!=2 && go(x - 1, y, ans))
return true;
if (y > 0)
if (puz\[x\]\[y-1\]!=2 && go(x, y - 1, ans))
return true;
//path.pop();
puz\[x\]\[y\] = 3;
return false;
}
public:
puzzle(int n):length(n) {
puz = new int*[n];
for (int i = 0; i < n; i++) {
puz[i] = new int[n] {0};
}
}
void print(int time=0) {
for (int i = 0; i < length + 2; i++) {
for (int j = 0; j < length + 2; j++) {
if (i == 0 || j == 0 || i == length + 1 || j == length + 1) {
setfillcolor(BROWN);
fillrectangle(10 * i, 10 * j, 10 * (i + 1), 10 * (j + 1));
}
else {
if (puz\[i - 1\]\[j - 1\] == 1) {
setfillcolor(RED);
fillrectangle(10 * i, 10 * j, 10 * (i + 1), 10 * (j + 1));
}
else if (puz\[i - 1\]\[j - 1\] == 2) {
setfillcolor(YELLOW);
fillcircle(10 * i+5, 10 * j+5, 5);
}
else if (puz\[i - 1\]\[j - 1\] == 3) {
setfillcolor(BLUE);
fillrectangle(10 * i, 10 * j, 10 * (i + 1), 10 * (j + 1));
}
else {
setfillcolor(GREEN);
fillrectangle(10 * i, 10 * j, 10 * (i + 1), 10 * (j + 1));
}
}
}
cout << endl;
}
}
void mk(bool ans=1) {
formpuzzle(0, 0, length, length, ans);
}
void go_loop() {//非递归算法
pointStack s;
stkpoint w;
w.p = new point(0, 0);
point *q;
while (true) {
bool poped = false;
if (puz\[w.p->x\]\[w.p->y\] ==0) {
puz\[w.p->x\]\[w.p->y\] = 2;
//print();
s.push(w);
}
else {
poped = true;
w = s.pop();
w.dir++;
}
if (w.p->x == length - 1 && w.p->y == length - 1)break;
if (w.dir < 8) {
if (poped)s.push(w);
if (w.p->x + direction\[w.dir\]\[0\] < length&&w.p->x + direction\[w.dir\]\[0\] >= 0 && w.p->y + direction\[w.dir\]\[1\] < length&&w.p->y + direction\[w.dir\]\[1\] >= 0) {
q = new point(w.p->x + direction\[w.dir\]\[0\], w.p->y + direction\[w.dir\]\[1\]);
w.p = q;
w.dir = 0;
}
}
else {
puz\[w.p->x\]\[w.p->y\] = 3;
if (!poped)s.pop();
}
}
}
void search(bool ans=1) {
go(0, 0, ans);
}
};
int main() {
int n,ans1,ans2;
cout << “请输入你需要的地图维度：”;
cin >> n;
cout << “是否需要输出创建过程？”;
cin >> ans1;
cout << “是否需要输出寻迹过程？”;
cin >> ans2;
srand(time(0));
int t = 2 n + 1;
initgraph(10 (t+2), 10 * (t+2));
puzzle puzz(t);
setfillcolor(YELLOW);
setbkcolor(BLUE);
puzz.print(1);
puzz.mk(ans1);
puzz.print(1);
if (!ans1)Sleep(1000);
//puzz.search(ans2);
puzz.go_loop();
puzz.print();
getchar();
getchar();
return 0;
}