برنامه حرکت موش در هزار تو – rat in a maze

rat-maze-cheese

برنامه حرکت موش در هزار تو (ماز) یا همون rat in maze  یکی از بهترین سوال های مربوط به ساختمان داده است که می توان از آن برای آموزش پشته (Queue) و استک (Stack) استفاده کرد .

در این برنامه قرار است یک موش در هزار تو قرار بگیرد و راه خود را به یک خانه ی خاص که پنیر در آن قرار دارد پیدا کند .مانند شکل زیر (رنگ سبز نقطه آغاز ،رنگ زرد پنیر ،رنگ سفید هم دیوار است):

rat0

ما در این پست موش را با استفاده از صف (Queue) به پنیر می رسانیم و اینگونه عمل می کنیم :

ابتدا خانه های اطراف خانه ی شروع را با مقدار یک پر می کنیم :

rat1بعد از اینکه این دو خانه را پر کردیم آن ها را در صف پوش  (PUSH) می کنیم ، در مرحله بعد یکی از خانه ها را از صف می خوانیم و خانه های اطراف آن را با مقدار ۲ پر می کنیم و خانه هایی را که پر کرده ایم درون صف پوش می کینم و بعد یک خانه ی دیگر از استک می خوانیم و این کار را دوباره و دوباره انجام می دهیم تا به پنیر برسیم مانند شکل های زیر:

rat2

rat4

rat5rat6

rat8مسییر زرد نشان دهنده راه موش است .در برنامه ای که کدش در پایین آمده در قسمت make map  (ساختن نقشه) فرد یک نقشه ایجاد می کند که نقشه یک آرایه دو در دو از اعداد صحیح است و مقدار -۱ نشان دهنده دیوار ،مقدار -۲ نشان دهنده پنیر یا همان خانه هدف است و عدد -۳ که بعد از فراخوانی تابع solve در آرایه قرار می گیرد مسیر را مشخص می کند

و این هم کد برنامه حرکت موش در هزار تو Rat in maze  با زبان سی پلاس پلاس :

 

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۱۷ دیدگاه

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *