题目
问题描述
在平面上有一些二维的点阵.
这些点的编号就像二维数组的编号一样,从上到下依次为第1至第n行。从左到右依次为第1至第m列,每一个点可以用行号和列号来表示。
现在有个人站在第1行第1列,要走到第n行第m列。只能向右或者向下走。
注意,如果行号和列号都是偶数,不能走入这一格中。
问有多少种方案。
输入格式
输入一行包含两个整数n,m。
输出格式
输出一个整数,表示答案。
样例输入
3 4
样例输出
2
思路
看见走方格的题,首先就想到了用dfs或bfs来解决,但是该题并不是求最短路,而是有多少种到终点的走法,此时只用dfs或bfs就会出现大量重复的计算而引发超时,所以还需要用到动规,用一个二维数组存放每个点到终点有多少种走法,由题意只能向右或向下走可以得出,第map[i][j]点就有map[i+1][j]+map[i][j+1]种走到终点的方案。
代码
#include<iostream>
using namespace std;
long long map[25][25]; //存储map[i,j]点有多少种方案走到n,m
int n,m;
long long dfs(int i,int j){
if(i > n||j >> m)return 0; //越界
if(i==n&&j==m)return 1; //走到终点
if(i%2==0&&j%2==0)return 0; //不能走的点
if(map[i][j]!=0)return map[i][j]; //计算过
map[i][j] = dfs(i+1,j) + dfs(i,j+1);
return map[i][j];
}
int main(){
cin >> n >> m;
cout << dfs(1,1);
return 0;
}