Real topic of the 2020 Landbridge cup provincial competition - go square (dp/dfs)

Original link ： Go through the squares

Topic overview ：
There are some two-dimensional lattices in the plane .
These points are numbered just like a two-dimensional array , From the top to the bottom is 1 To That's ok , From left to right, the order is 1 To Column , Each dot can be represented by line number and column number .
Now there's a man standing at number one 1 Xing di 1 Column , To go to the first Xing di Column .
You can only go right or down .
Be careful , If the row number and column number are even , You can't go into this space .
Ask how many options .

Ideas

As soon as you see the problem maze algorithm to find the maximum and minimum value, you must first consider whether to use dynamic programming to solve , Obviously, the question can be used DP Work it out , besides , If you can't use dynamic programming, you should consider using DFS perhaps BFS solve .

First , This topic uses DP The solution is very simple , It's a simple two-dimensional DP. We define dp[i][j] Go to the first place i Xing di j Number of options listed , And you can only go right or down at a time , From this we can write the state transition equation dp[i][j]=dp[i-1][j]+dp[i][j-1]（ From left and up to the current position ） Particular attention ： When i And j Even numbers dp[i][j]=0

DP Code ：

#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;
}

except DP In addition to the solution, you can also use extensive search to record the total number of schemes ,DFS The code is as follows ：

#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;
}

Blue Bridge Cup provincial tournament is coming , If you are reading this article, you are also preparing for the Blue Bridge Cup ^ - ^, Come on, everybody ！！！