题目

问题描述

  在平面上有一些二维的点阵.
  这些点的编号就像二维数组的编号一样,从上到下依次为第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;
}
最后修改:2020 年 07 月 06 日
如果觉得我的文章对你有用,请随意赞赏