l 時間為種子。白色格子10%概率生成。綠色和紅色子塊的坐標隨機生成。 srand((unsigned)time(NULL)); //以時間為隨機種子 for(i=1;i<=size;i++) { for(j=1;j<=size;j++) { if(1==rand()%10) //10%摡率達成 g ...
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頭文件中的函數，設置了方塊背景色。見另隨筆。
