題目描述

在平面上有一些二維的點陣。

這些點的編號就像二維數組的編號一樣，從上到下依次為第 1 至第 行，從左到右依次為第 1 至第 列，每一個點可以用行號和列號來表示。

現在有個人站在第 1 行第 1 列，要走到第 行第 列。

只能向右或者向下走。

注意，如果行號和列數都是偶數，不能走入這一格中。

問有多少種方案。

輸入

輸入一行包含兩個整數 。

輸出

輸出一個整數，表示答案。

樣例輸入

3 4

樣例輸出

2

提示

1<=n,m<=30

方法一：遞歸

import java.util.Scanner; public class Main {public static void main(String[] args) { Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();int count=dfs(1,1,n,m);System.out.print(count);}public static int dfs(int i,int j,int n,int m){if(i%2==0&&j%2==0){return 0;}if(i==n&&j==m){return 1;} if(i==n){return dfs(i,j+1,n,m);}if(j==m){return dfs(i+1,j,n,m);}return dfs(i,j+1,n,m)+dfs(i+1,j,n,m);} }

分析

我看到題目首先想到的方法思想就是遞歸，一開始，只有兩條路可以走，向下走或者向右走，然后再向下走或者向右走…

我們可以構出遞歸的函數，當遞歸到 i=n,j=m 的時候，return 1，這個1就是，找到了1條路。

當i=n的時候只能向右走，當j=m的時候只能向下走，那就繼續遞歸，分別return dfs(i,j+1,n,m)、return dfs(i+1,j,n,m);

除了這兩種情況以外，既可以向下走也可以向右走，那就繼續遞歸，return dfs(i,j+1,n,m)+dfs(i+1,j,n,m) 。 因為兩條路都可以走所以相加就可以了，根據最后return的值加起來得到最終的值。

重點來了，當 i 和 j 都是偶數的時候，不能走這個格子，那么在遞歸中就要結束它，這條路行不通，那就不能加1，所以return 0

當n和m都是偶數的時候，這個格子都走不進去，那自然沒有路啦！（所以，要把return 0 放在return 1 的上面）

方法二：動態規劃

import java.util.Scanner; public class Main {public static void main(String[] args) { Scanner sc=new Scanner(System.in);int n=sc.nextInt(),m=sc.nextInt();int[][] dp=new int[n+1][m+1];for(int i=1;i<=n;i++){ //第一列全為1dp[i][1]=1;}for(int i=1;i<=m;i++){ //第一行全為1dp[1][i]=1;}for(int i=2;i<=n;i++){for(int j=2;j<=m;j++){if(i%2!=0||j%2!=0)dp[i][j]=dp[i][j-1]+dp[i-1][j];}}System.out.print(dp[n][m]);} }

分析

算法思路是看了xpq的寫的算法，因為用上面方法一遞歸AC了題目后就沒想太多了，不過這種思路的算法還是蠻不錯的！

定義二維數組，元素值表示 能夠進入該格子的路徑有幾條。

首先，我們可以在草稿紙上畫出n*m的格子，這里假設n=3，m=4。從第一行第一列（咱舍去第0行列）開始，我們可以發現第一行的每個格子能進入的路徑數都是1。比如說，（1,2）第一行第二列的格子，它只能由一條路進入過來，那就是從（1,1）過來的，因為只能向下和向右走。

我們可以設想一下。第一行第三列的格子，它的上下左右有哪些格子可以從該格子走到第一行第三列的格子，前提是每個格子只能向下和向右走！！

同理，第一列的每個格子能進入的路徑數也都是1。

行列都為偶數的格子，值都為0，也就是0條路。進都進不去

這會兒分析到這，應該能推算出，其他格子的路徑數了吧，剩下每個格子的路徑數為：左邊格子的路徑數+上面格子的路徑數。因為只有左邊的格子和上面的格子才能到本格子里來。

總結

以上是生活随笔為你收集整理的蓝桥杯2020年第十一届省赛真题-走方格-java的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。