蓝桥杯11届B组H题-走方格

题目

问题描述

  在平面上有一些二维的点阵.
  这些点的编号就像二维数组的编号一样,从上到下依次为第1至第n行。从左到右依次为第1至第m列,每一个点可以用行号和列号来表示。
  现在有个人站在第1行第1列,要走到第n行第m列。只能向右或者向下走。
  注意,如果行号和列号都是偶数,不能走入这一格中。
  问有多少种方案。

输入格式

输入一行包含两个整数n,m。

输出格式

输出一个整数,表示答案。

样例输入

3 4

样例输出

2

思路

看见走方格的题,首先就想到了用dfs或bfs来解决,但是该题并不是求最短路,而是有多少种到终点的走法,此时只用dfs或bfs就会出现大量重复的计算而引发超时,所以还需要用到动规,用一个二维数组存放每个点到终点有多少种走法,由题意只能向右或向下走可以得出,第mapi点就有mapi+1+mapi种走到终点的方案。

代码

#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;
}
本文作者:六月丶

本文链接:https://www.hctra.cn/index.php/archives/653/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2020 年 07 月 06 日 05 : 41 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论