简答题
偏难
#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 <cstdio>
#include <iostream>
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 < 1 || x > n || y < 1 || y > m; }
void fuzhi(int step) {
ans++;
a[ans] = step;
flag = true;
for (int i = 0; i <= 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 && y == m) {
fuzhi(step);
return;
}
for (int i = 0; i < 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 >> n >> m;
dfs(1, 1, 0);
printf("%d\n", ans);
for (int i = 1; i <= ans; i++)
return 0;
}</pre>
这道题暂未补解析。