首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#7486

移动路线(2023.12) 桌子上有一个m行n列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为(1,1),…

移动路线(2023.12)

桌子上有一个m行n列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为(1,1),则右上角方格的坐标为(m,n)。

小明是个调皮的孩子,一天他捉来一只蚂蚁,不小心把蚂蚁的右脚弄伤了,于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中,蚂蚁从左下角的方格中移动到右上角的方格中,每步移动一个方格。蚂蚁始终在方格矩阵内移动,请计算出不同的移动路线的数目。

对于1行1列的方格矩阵,蚂蚁原地移动,移动路线数为1;对于1行2列(或2行1列)的方格矩阵,蚂蚁只需一次向右(或向上)移动,移动路线数也为1……对于一个2行3列的方格矩阵,如下图所示:

-------------------

|(2,1)|(2,2)|(2,3)|

-------------------

|(1,1)|(1,2)|(1,3)|

-------------------

蚂蚁共有3种移动路线:

路线1:(1,1) → (1,2) → (1,3) → (2,3)

路线2:(1,1) → (1,2) → (2,2) → (2,3)

路线3:(1,1) → (2,1) → (2,2) → (2,3)

时间限制:1000

内存限制:65536

输入

输入只有一行,包括两个整数m和n(0<m+n<=20),代表方格矩阵的行数和列数,m、n之间用空格隔开

输出

输出只有一行,为不同的移动路线的数目。


样例输入

2 3

样例输出

3
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">// C++参考代码1 #include &lt;cstdio&gt; #include &lt;iostream&gt; using namespace std; const int N = 40; const int dx[2] = {0, 1}; const int dy[2] = {1, 0}; int n, m, ans = 0; bool flag = false; struct node {   int x;   int y; } st[N * N], tu[N * N][N * N]; int a[N * N]; bool ran_out(int x, int y) { return x &lt; 1 || x &gt; n || y &lt; 1 || y &gt; m; } void fuzhi(int step) {   ans++;   a[ans] = step;   flag = true;   for (int i = 0; i &lt;= step; i++) {     tu[ans][i].x = st[i].x;     tu[ans][i].y = st[i].y;   } } void dfs(int x, int y, int step) {   st[step].x = x;   st[step].y = y;   if (x == n &amp;&amp; y == m) {     fuzhi(step);     return;   }   for (int i = 0; i &lt; 2; i++) {     int xx = x + dx[i];     int yy = y + dy[i];     if (!ran_out(xx, yy)) {       dfs(xx, yy, step + 1);     }   } } int main() {   std::ios::sync_with_stdio(false);   cin &gt;&gt; n &gt;&gt; m;   dfs(1, 1, 0);   printf("%d\n", ans);   for (int i = 1; i &lt;= ans; i++)     return 0; }</pre><pre class="brush:cpp;toolbar:false">// C++参考代码2 #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; int countRoutes(int m, int n) {     vector&lt;vector&lt;int&gt;&gt; dp(m, vector&lt;int&gt;(n, 1));     for (int i = 1; i &lt; m; i++) {         for (int j = 1; j &lt; n; j++) {             dp[i][j] = dp[i-1][j] + dp[i][j-1];         }     }     return dp[m-1][n-1]; } int main() {     int m, n;     cin &gt;&gt; m &gt;&gt; n;     int result = countRoutes(m, n);     cout &lt;&lt; result &lt;&lt; endl;     return 0; }</pre><pre class="brush:cpp;toolbar:false">// C语言参考代码 #include &lt;stdio.h&gt; int countRoutes(int m, int n) {     // 创建一个二维数组用于存储移动路线数     int routes[m][n];     // 初始化边界条件     for (int i = 0; i &lt; m; i++) {         routes[i][0] = 1;     }     for (int j = 0; j &lt; n; j++) {         routes[0][j] = 1;     }     // 计算每个方格的移动路线数     for (int i = 1; i &lt; m; i++) {         for (int j = 1; j &lt; n; j++) {             routes[i][j] = routes[i-1][j] + routes[i][j-1];         }     }     // 返回右上角方格的移动路线数     return routes[m-1][n-1]; } int main() {     int m, n;     scanf("%d %d", &amp;m, &amp;n);     int result = countRoutes(m, n);     printf("%d\n", result);     return 0; }</pre>
这道题暂未补解析。