1 #include<iostream>
2 #include<queue>
3 #include<windows.h>
4 #include<time.h>
5 using namespace std;
6 struct position
//位置
7 {
8 int row;
9 int col;
10 };
11 void display(
int size,
int **
grid);
12
13 int main()
14 {
15
16 /*****************************产生随机MAZE，并显示************************************/
17 int size,i,j,p,q,m,n;
18 int **
grid;
19 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_INTENSITY|FOREGROUND_RED|
20 FOREGROUND_GREEN|FOREGROUND_BLUE);
//白色
21 cout<<
"please enter the size(边长)of square!(size<100)"<<
endl;
22 cin>>
size;
23 grid=
new int *[size+
2];
//动态创建二维数组
24 for(i=
0;i<size+
2;i++
)
25 {
26 grid[i] =
new int[size+
2];
//这个指针数组的每个指针元素又指向一个数组。
27 }
28 for(i=
0;i<size+
2;i++
)
29 {
30 grid[i][
0]=
'y';grid[
0][i]=
'y';
31 grid[size+
1][i]=
'y';grid[i][size+
1]=
'y';
32 }
33 srand((unsigned)time(NULL));
//以时间为随机种子
34 for(i=
1;i<=size;i++
)
35 {
36 for(j=
1;j<=size;j++
)
37 {
38
39 if(
1==rand()%
10)
//10%摡率达成
40 grid[i][j]=
'y';
41 else
42 grid[i][j]=
0;
43 }
44 }
45 p=rand()%size+
1;
46 q=rand()%size+
1;
//随机起点、终点
47 grid[p][q]=
'g';
48 m=rand()%size+
1;
49 n=rand()%size+
1;
50 grid[m][n]=
'r';
51
52 display(size,grid);
53 /**********************************找路********************************
54 把nbr都压入queue，一个一个弹出在找一下nbr，再压入，直到终点**********************/
55 position offset[
4];
//方向
56 offset[
0].row=
1;offset[
0].col=
0;
//right
57 offset[
1].row=
0;offset[
1].col=-
1;
//down
58 offset[
2].row=-
1;offset[
2].col=
0;
//left
59 offset[
3].row=
0;offset[
3].col=
1;
//up
60
61 position here;
62 position nbr;
63 position finish;
64 queue<position>
Q;
65
66 //初始化
67 here.row=p;here.col=
q;
68 finish.row=m;finish.col=
n;
69 grid[here.row][here.col]=
0;
70 while(
true){
71 for(i=
0;i<
4;i++
)
72 {
73 nbr.row=here.row+
offset[i].row;
74 nbr.col=here.col+
offset[i].col;
75 if((nbr.row==finish.row)&&(nbr.col==
finish.col))
76 { grid[finish.row][finish.col]=grid[here.row][here.col]+
1;
77 break;
78 }
79 else if(grid[nbr.row][nbr.col]==
0)
80 {grid[nbr.row][nbr.col]=grid[here.row][here.col]+
1;
81 Q.push(nbr);}
//符合条件的nbr都压进去
82
83 }
84 if((nbr.row==finish.row)&&(nbr.col==
finish.col))
85 { grid[finish.row][finish.col]=grid[here.row][here.col]+
1;
86 break;
87 }
88 if(Q.empty())
89 {
90 cout<<
"no path!"<<
endl;
91 break;
92 }
93 here=Q.front();
//取出front
94 Q.pop();
95
96 };
97 /****************************建造最短路径****************
98 从终点往回看，每次循环都看和终点计数的差值****************/
99 here=
finish;
100 int length=
grid[finish.row][finish.col];
101 for(j=
1;j<length;j++
)
102 {
103 for(i=
0;i<
4;i++
)
104 {
105 nbr.row=here.row+
offset[i].row;
106 nbr.col=here.col+
offset[i].col;
107 if(grid[nbr.row][nbr.col]==(grid[finish.row][finish.col]-
j))
108 {
109 grid[nbr.row][nbr.col]=
'p';
//你都把值改了下一循环成了p-1
110 here=
nbr;
111 break;
112 }
113 }
114 }
115 /**********************display**********************************/
116 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),BACKGROUND_INTENSITY |BACKGROUND_RED|
117 BACKGROUND_GREEN | BACKGROUND_BLUE);
//白色
118 cout<<
"Show you the shortest path!"<<
endl;
119 grid[p][q]=
'g';
120 grid[m][n]=
'r';
121 display(size,grid);
122 return 0;
123 }
124
125 /*********************显示函数***************************************/
126 void display(
int size,
int **
grid)
127 {
int i,j;
128 for(i=
0;i<size+
2;i++
)
129 {
130 for(j=
0;j<size+
2;j++
)
131 {
132 if(grid[i][j]==
'y')
133 {
134 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),BACKGROUND_INTENSITY|BACKGROUND_RED|
135 BACKGROUND_GREEN);
//黄色
136 cout<<
' '<<
' ';
137 }
138
139 else if(grid[i][j]==
'g')
140 {
141 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),BACKGROUND_INTENSITY |
142 BACKGROUND_GREEN);
//绿色
143 cout<<
' '<<
' ';
144 }
145 else if(grid[i][j]==
'r')
146 {
147 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),BACKGROUND_INTENSITY |
148 BACKGROUND_RED);
//红色
149 cout<<
' '<<
' ';
150 }
151 else if(grid[i][j]==
'p')
152 {
153 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),BACKGROUND_INTENSITY |
154 BACKGROUND_GREEN |
BACKGROUND_BLUE);
155 cout<<
' '<<
' ';
156 }
157 else
158 { SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),BACKGROUND_INTENSITY |BACKGROUND_RED|
159 BACKGROUND_GREEN | BACKGROUND_BLUE);
//白色
160 cout<<
' '<<
' ';
161 }
162
163 }
164 cout<<
endl;
165 }
166 }
l 时间为种子。白色格子10%概率生成。绿色和红色子块的坐标随机生成。
srand((unsigned)time(NULL)); //以时间为随机种子
for(i=1;i<=size;i++)
{
for(j=1;j<=size;j++)
{
if(1==rand()) //10%摡率达成
grid[i][j]='y';
else
grid[i][j]=0;
}
}
p=rand()%size+1;
q=rand()%size+1; //随机起点、终点
grid[p][q]='g'; //绿色
m=rand()%size+1;
n=rand()%size+1;
grid[m][n]='r'; //红色
l Queue:把符合条件的nbr都压入队列，每次弹出一个作为新的here再寻找nbr，直到找到终点。同时如果队列为空，输出no path！并跳出。（具体见程序）
l 颜色设置利用windos.h头文件中的函数，设置了方块背景色。见另随笔。
转载于:https://www.cnblogs.com/tenderwx/p/5321926.html
相关资源：数据结构—成绩单生成器
