1194：移動路線

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 8697 ??? 通過數: 6620

【題目描述】

X桌子上有一個m行n列的方格矩陣，將每個方格用坐標表示，行坐標從下到上依次遞增，列坐標從左至右依次遞增，左下角方格的坐標為(1,1)，則右上角方格的坐標為(m,n)。

小明是個調皮的孩子，一天他捉來一只螞蟻，不小心把螞蟻的右腳弄傷了，于是螞蟻只能向上或向右移動。小明把這只螞蟻放在左下角的方格中，螞蟻從

? ?左下角的方格中移動到右上角的方格中，每步移動一個方格。螞蟻始終在方格矩陣內移動，請計算出不同的移動路線的數目。

? ?對于1行1列的方格矩陣，螞蟻原地移動，移動路線數為1；對于1行2列（或2行1列）的方格矩陣，螞蟻只需一次向右（或向上）移動，移動路線數也為1……對于一個2行3列的方格矩陣，如下圖所示：

?

【輸入】

輸入只有一行，包括兩個整數m和n（0 < m+n ≤ 20），代表方格矩陣的行數和列數，m、n之間用空格隔開。

【輸出】

輸出只有一行，為不同的移動路線的數目。

【輸入樣例】

2 3

【輸出樣例】

3

【分析】

? ? ? ? 設a[i][j]為螞蟻爬到坐標(i,j)的方案數，螞蟻只能向上或向右移動，即矩陣中，遞推關系式為：a[i][j] = a[i-1][j] + a[i][j-1]，遞推邊界為：對于1行i 列的方格矩陣，螞蟻原地移動，移動路線數為1；對于 i 行1列的方格矩陣，螞蟻移動路線為1，故a[1][i]=1，a[i][1]=1。

【參考代碼】

#include <stdio.h> int main() {int a[22][22]={0};int i,j,m,n;scanf("%d%d",&m,&n);for(i=1;i<20;i++) ? //初始化，當只有一列或者只有一行的時候只有一種方法{a[1][i]=1;a[i][1]=1;}for(i=2;i<20;i++){for(j=2;j<20;j++){a[i][j]=a[i-1][j]+a[i][j-1]; ? //找到的規律}}printf("%d\n",a[m][n]);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1194

?

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1194：移动路线）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。