2020年蓝桥杯省赛真题-走方格(DP/DFS)

原题链接： 走方格

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

思路

一看到题目迷宫算法求最大值最小值的时候首先就要去考虑是不是要用动态规划求解，很显然该题可以用DP解出来，除此之外，如果不能用动态规划就要考虑用DFS或者BFS求解。

首先，本题用DP解法很简单，就是一个简单二维DP。我们定义dp[i][j]表示走到第i行第j列的方案数，并且每次只能向右或向下走，由此我们可以写出状态转移方程dp[i][j]=dp[i-1][j]+dp[i][j-1]（从左和从上走到目前位置的方案和）特别注意：当i与j都是偶数的时候dp[i][j]=0

DP代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 35;
int dp[N][N];
int n,m;

int main()
{
    
    cin>>n>>m;
    for(int i=1;i<=n;i++)dp[i][1]=1;
    for(int j=1;j<=m;j++)dp[1][j]=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]=0;
            else dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    
    cout<<dp[n][m]<<endl;
}

除了DP解法外还可以用广搜来记录总方案数，DFS代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 35;
int mp[N][N];
int vis[N][N];
int dx[2]={
    0,1};
int dy[2]={
    1,0};
int n,m,ans;
bool in(int x,int y)
{
    
    if(x<1||x>n||y<1||y>m)return false;
    else return true;
}
void dfs(int x,int y)
{
    
    if(x==n&&y==m)
    {
    
        ans++;
        return;
    }
    vis[x][y]=1;
    for(int i=0;i<2;i++)
    {
    
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(in(nx,ny)&&!vis[nx][ny]&&mp[nx][ny]==0)
            dfs(nx,ny);
    }
    vis[x][y]=0;
}
int main()
{
    
    cin>>n>>m;
    ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(i%2==0&&j%2==0)mp[i][j]=1;
            else mp[i][j]=0;
    dfs(1,1);
    cout<<ans<<endl;
}

蓝桥杯省赛将至，如果你在看这篇文章的话说明你也在备战蓝桥杯吧^ - ^，大家一起加油！！！