简答题 偏难
#7222

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

移动路线

桌子上有一个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">#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>
这道题暂未补解析。