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) //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頭文件中的函數，設置了方塊背景色。見另隨筆。
