走方格（蓝桥杯2020年试题H）

     【题目形貌】在平面上有一些二维点阵。这些点的编号就像二维数组的编号一样，从上到下依次为第1~n行，从左到右依次为第1~m列，每个点可以用行号和列号表示。
     现在有个人站在第1行第1列，他要走到第n行第m列，只能向右或者向下走。
    【注意】如果行号和列数都是偶数，则不能走入这一格。
     问有多少种方案。
  【输入格式】
     一行，包含两个整数n和m。
   【输出格式】
     一个整数，表示答案。
   【样例输入】
     20    21
  【样例输出】
     92378
 【数据规模】
    数据范围为 n >= 1， m <= 30。
【解析】
      设n=5，m=5，则本题的示意图如下图所示，方格中共有4个方格不能走入，其他方格可以通过向下和向右走入。
    本题可以接纳动态规划的方法办理。

       

     设f[j]表示走到第i行，第j列时的走法数目，那么走到f[j]的方法只有两种，即从上面走过来的或者从左边走过来，故[j]的做法是这两种走法之和，即，
       f[j] = f[i-1][j] + f[j-1]
    这也是状态转移方程，需要注意以下两点。
   （1）该状态转移方程必须满足i和j不同时为偶数，同，如果i和j同时为偶数，则该方格的走法为0。
   （2）初始状态为f[1][1]=1，即到达f[1][1]一共有1种方法。
【参考步伐如下】

1. #include <iostream>
2. using namespace std;
3. int n,m,ans;
4. int i,j;
5. int f[35][35];
6. int main(int argc, char** argv) {
7.         cin >> n >> m;
8.         if(n % 2 == 0 && m % 2 == 0)
9.         {
10.                 cout << 0;
11.                 return 0;
12.         }
13.         for(i = 1; i <= n; i++)
14.             for(j = 1; j <= m;j++)
15.             {
16.                     if(i == 1 && j == 1)
17.                     f[i][j] = 1;
18.                     //初始化
19.                         else if(i % 2 == 1 || j % 2 == 1) //方格不全为偶数
20.                         f[i][j] = f[i - 1][j] + f[i][j - 1];
21.                 }
22.                 cout << f[n][m] << endl;
23.         return 0;
24. }

复制代码

【步伐运行结果如下】

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。