اگه صورت مساله رو راحت تر کنی راه حل رو راحت بدست میاری.فرض کن این خونه 3 در 3 باشه.:
کد:
[a][x][x]
[x][x][x]
[x][x][b]
چون فقط مسیر به پایین و راست مجازه, تنها راه رسیده به b دو بار حرکت به راست و 2 بار حرکت به پایین توی حالت های مختلف هست.اگر R رو بگیریم حرکت به راست و D رو بگیریم حرکت به پایین, مساله این طوری میشه که R, R, D, D رو به چند صورت و چه صورت هایی میتونیم کنار هم بگذاریم؟
اگه خونه ی ما M سطر و N ستون داشته باشه, N-1 تا R و M-1 تا D داریم و باید مساله رو برای این مقدار ها حل کنیم.
قسمت اول یعنی" چند صورت" مثل یه مساله ی احتمال حل میشه:
کد:
(N - 1 + M - 1) ! / ( (N - 1)! x (M - 1) ! )
که ! علامت فاکتوریل هست که با پیاده سازیش توی C میشه جواب این قسمت رو راحت حساب کرد.
اما قسمت مشکل تر پیدا کردن کل راه هاست:
بدست آوردن راه هایی که میشه (M-1) تا R و (N-1) تا D رو کنار هم گذاشت.
خودم یکم زور زدم که بنویسمش اما الان 6 صبحه و من هنوز نخوابیدم مخم نمیکشه.
شاید اینایی که گفتم رو خودت میدونستی ولی به هر حال نوشتم تا بعدا دوباره نخوام بدستشون بیارم!