题目描述
在平面上有一些二维的点阵。
这些点的编号就像二维数组的编号一样,从上到下依次为第 1 至第 n 行,从左到右依次为第 1 至第 m 列,每一个点可以用行号和列号来表示。
现在有个人站在第 1 行第 1 列,要走到第 n 行第 m 列。
只能向右或者向下走。
注意,如果行号和列数都是偶数,不能走入这一格中。
问有多少种方案。
输入格式
输入一行包含两个整数 n,m。
输出格式
输出一个整数,表示答案。
数据范围
1≤n,m≤30
输入样例1:
3 4
输出样例1:
2
输入样例2:
6 6
输出样例2:
0
算法1
(动态规划) $O(2*n*n)$
y总说过先看数据,发现数据只有30个,那么暴力解决即可;
这里的走法的话,在第一行,和第一列都是1;特判就可以。
另外它说行列都是偶数的话就不能走,那么我们运用一个数组记录看看能不能走,为什么不在dp数组上进行操作,因为在dp数组上修改会破坏原来的更新递推顺序
时间复杂度
参考文献
C++ 代码
#include <iostream>
using namespace std;
int dp[32][32];
bool b[32][32];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if((i%2==0)&&(j%2==0))
{
b[i][j]=true;//不能走
}
}
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(b[i][j])
{
dp[i][j]=0;//不能走dp就是0,没有走过来的步数,剩下不更新;
continue;
}
else if(i==1) dp[i][j]=1;
else if(j==1) dp[i][j]=1;
else dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
cout<<dp[n][m]<<endl;
return 0;
}
算法2
(dfs) $O(n)$
直接搜索加上一个限制就可以了
时间复杂度
参考文献
C++ 代码
#include <stdio.h>
int n, m;
int ans;
void dfs(int x, int y) // 搜索 (x, y)
{
if(x & 1||y & 1)
{
if(x==n&&y==m)
{
ans++;
return ;
}
if(x<n) dfs(x+1,y);
if(y<m) dfs(x,y+1);
}
}
int main()
{
scanf("%d%d", &n, &m);
dfs(1, 1); // 从点 (1, 1) 开始搜索
printf("%d\n", ans);
return 0;
}