مسئله حرکت موش در هزار تو
برنامه حرکت موش در هزارتو یا همان rat in maze یکی از بهترین سوال های مربوط به ساختمان داده است که می توان از آن برای آموزش پشته (Queue) و استک (Stack) استفاده کرد.
تعریف مسئله موش در هزارتو
در این برنامه قرار است یک موش در هزار تو قرار بگیرد و راه خود را به یک خانه ی خاص که پنیر در آن قرار دارد پیدا کند .مانند شکل زیر (رنگ سبز نقطه آغاز ،رنگ زرد پنیر ،رنگ سفید هم دیوار است):
ما در این پست موش را با استفاده از صف (Queue) به پنیر می رسانیم و اینگونه عمل می کنیم :
ابتدا خانه های اطراف خانه ی شروع را با مقدار یک پر می کنیم :
بعد از اینکه این دو خانه را پر کردیم آن ها را در صف پوش (PUSH) می کنیم ، در مرحله بعد یکی از خانه ها را از صف می خوانیم و خانه های اطراف آن را با مقدار ۲ پر می کنیم و خانه هایی را که پر کرده ایم درون صف پوش می کینم و بعد یک خانه ی دیگر از استک می خوانیم و این کار را دوباره و دوباره انجام می دهیم تا به پنیر برسیم مانند شکل های زیر:
مسیر زرد نشان دهنده راه موش است .در برنامه ای که کدش در پایین آمده در قسمت make map (ساختن نقشه) فرد یک نقشه ایجاد می کند که نقشه یک آرایه دو در دو از اعداد صحیح است و مقدار -۱ نشان دهنده دیوار ،مقدار -۲ نشان دهنده پنیر یا همان خانه هدف است و عدد -۳ که بعد از فراخوانی تابع solve در آرایه قرار می گیرد مسیر را مشخص می کند.
کد مسئله حرکت موش در هزاتو
و این هم کد برنامه حرکت موش در هزار تو Rat in maze با زبان سی پلاس پلاس :
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 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 | // rate in maze(queue).cpp //open-mind.ir #include <iostream> #include <queue> using namespace std; //class posistin contain int x for x-Axis and int y for y-Axis. //class position = cartesian coordinates; class position { public: int x; int y; position() { x = 0; y = 0; } position(int X,int Y) { x = X; y = Y; } }; //------------------------Show------------------------- void show(int **A,int row,int col) { char ch = 178; for (int i = 0; i < col+1; i++) { cout<<ch<<ch; } cout<<ch; cout<<endl; for (int i = 0; i < row; i++) { cout<<ch<<" "; for (int j = 0; j < col; j++) { if (A[i][j] == -1) { cout<<ch<<ch; continue; } if (A[i][j] == -3) { cout<<"."<<" "; continue; } if (A[i][j] == -2) { cout<<"*"<<" "; continue; } cout<<" "; } cout<<ch<<" "; cout<<endl; } for (int i = 0; i < col+1; i++) { cout<<ch<<ch; } cout<<ch; cout<<endl; } //----------------------------------------------------- //this function take: //int **A : this is map of maze. -1 for wall , -2 for Goalpoint and -3 for way that put in array after solve //int row : this is number of row. //int col : this is number of col. //int start: start position. void solve(int **A,int row,int col,position start) { //char ch; queue<position> que; position temppos; bool ExistWay = false; A[start.x][start.y] = 1; que.push(start); while (que.size() != 0) { temppos = que.front(); //cout<<"*********"<<endl; que.pop(); if (temppos.x > 0) { if (A[temppos.x-1][temppos.y] == 0 || A[temppos.x-1][temppos.y] == -2) { if (A[temppos.x-1][temppos.y] == -2) { ExistWay = true; break; } A[temppos.x-1][temppos.y] = A[temppos.x][temppos.y] + 1; que.push(position(temppos.x-1,temppos.y)); } //show(A,row,col); //cin>>ch; } if (temppos.x < row-1) { if (A[temppos.x+1][temppos.y] == 0 || A[temppos.x+1][temppos.y] == -2) { if (A[temppos.x+1][temppos.y] == -2) { ExistWay = true; break; } A[temppos.x+1][temppos.y] = A[temppos.x][temppos.y] + 1; que.push(position(temppos.x+1,temppos.y)); } //show(A,row,col); //cin>>ch; } if (temppos.y > 0) { if (A[temppos.x][temppos.y-1] == 0 || A[temppos.x][temppos.y-1] == -2) { if (A[temppos.x][temppos.y-1] == -2) { ExistWay = true; break; } A[temppos.x][temppos.y-1] = A[temppos.x][temppos.y] + 1; que.push(position(temppos.x,temppos.y-1)); } //show(A,row,col); //cin>>ch; } if (temppos.y < col-1) { if (A[temppos.x][temppos.y+1] == 0 || A[temppos.x][temppos.y+1] == -2) { if (A[temppos.x][temppos.y+1] == -2) { ExistWay = true; break; } A[temppos.x][temppos.y+1] = A[temppos.x][temppos.y] + 1; que.push(position(temppos.x,temppos.y+1)); } //show(A,row,col); //cin>>ch; } } if (ExistWay == false) { cout<<"No way to target!"<<endl; } else { int p; int q = A[temppos.x][temppos.y]; for (int i = 0; i < q; i++) { p = A[temppos.x][temppos.y]-1; A[temppos.x][temppos.y] = -3; if (temppos.x > 0) { if (A[temppos.x-1][temppos.y] == p) { temppos = position(temppos.x-1,temppos.y-1); } } if (temppos.x < row-1) { if (A[temppos.x+1][temppos.y] == p) { temppos = position(temppos.x+1,temppos.y); } } if (temppos.y > 0) { if (A[temppos.x][temppos.y-1] == p) { temppos = position(temppos.x,temppos.y-1); } } if (temppos.y < col-1) { if (A[temppos.x][temppos.y+1] == p) { temppos = position(temppos.x,temppos.y+1); } } } } show(A,row,col); } //----------------------------------------------------------- int main() { //-----------------Start-Make-Map------------------ //------------------------------------------------- int row = 10; int col = 10; int **A; //Map position start(0,0); //coordination of start point A = new int *[row]; for (int i = 0; i < col; i++) { A[i] = new int [col]; } for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { A[i][j] = 0; } } A[1][1] = A[1][2] = A[1][3] = A[1][4] = A[0][4] = A[2][1] = A[4][1] = A[5][1] = A[5][0] = -1;//For Wall A[3][4] = A[3][5] = A[3][6] = A[3][6] = -1;//For Wall A[3][3] = A[4][3] = A[5][3] = A[6][3] = A[8][3] =-1;//For Wall A[8][3] = A[9][3] = -1;//For Wall A[8][5] = A[7][5] = -1; //For Wall A[8][8] = -2;//For Goal point //-----------------End-Make-Map-------------------- solve(A,row,col,start); return 0; } |
فوق العاده بود..خیلی خیلی سپاس از محبت بی کرانتون..خیلی به دردم خورد
واقعا ممنون از نشر علمتون و سخاوتمندی شما
سلام وقت بخیر ..
منظورم همون دوتا تعریف اول برنامه و تعریف حلقه ها واینا هستش؟
بله
سلام وقت بخیر..
ببخشید یعنی فقط سرفصل ها را باید تغییر بدم؟
باتشکر
منظورتون از سرفصل ها چیه ؟
سلام آقای دلیرانی
اگر بخواهیم maze را با c#بنویسیم چیکار کنیم؟
شما میتونید بهم کمکم کنید
ممنونتون میشم
۱سوال دیگه آقای جمالی هم از نویسندگان این وبسایت هستن؟
بله آقای جمالی از نویسندگان این وبسایت هستند ، همین برنامه سی پلاس پلاس رو عینا با سی شارپش معادل سازی کنید – چیز خاصی از سی پلاس نیست که توش باشه به همین خاطر معادل سازی اش بسیار آسان است.
سلام خسته نباشید
این برنامه mazeبه زبان c#است یا c++؟؟؟؟
سلام c++
سلام
باتشکر از مطالب بسیار مفیدتون!
میخواستم بدونم برای دریافت یک عدد مثل ده به نوان هزار باید چه کار کرد؟؟
باتشکر
سلام
بسته به زبان برنامه نویسی شما میتونه جواب فرق داشته باشه. در هر حال، اگه زبان برنامه نویسی مورد نظر شما نوع داده Big Number رو که معمولاً با اسم های این چنینی در زبان های مختلف وجود داره، پیاده سازی کرده باشه میتونین از اون استفاده کنید وگرنه باید با یک نوع داده مثل آرایه، خودتون ساختاری (در زبان های شئ گرا) پیاده سازی کنید که بتونه اعداد بزرگ رو در خودش نگه داره.
mersi, mersi mersi, mersi, mer siiiiiiiiiiiiiiiiiiiiiiii
tamame etelaate sitetoon fogholade mofid bood
khoda kheiretoon bede 🙂
با سلام
میشه بگید چطوری میشه ورودی های wall رو از طریق فایل خوند؟
اندیس محل هایی از آرایه رو که قرار است دیوار باشند رو از فایل با فرمت دلخواه بخون و در آرایه در اون محل ها -۱ قرار بده! به همین سادگی!
سلام
روش چهار همسایه چطوریه؟؟؟؟؟؟؟؟؟
نشنیدم تا حالا،ولی اگر فهمیدی به ما هم بگو