一个人的巴黎

用户名：uq_36478041918

访问量：15006

签　名：

等　　级
排　　名	105
经　　验	8307
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

编写题解 1132: 最大数问题数组通俗易懂
浏览：755

优秀的拆分,方法都会，注意细节即可，考察递归思想
浏览：361

奖学金，运用sort函数对结构体类型排序
浏览：283

你可能喜欢

蓝桥杯2020年第十一届省赛真题-走方格【DFS/DP】

　　作者: 一个人的巴黎　　　　发表时间：2022-03-12 21:29:36 浏览：769　|　评论：0　

原题链接：蓝桥杯2020年第十一届省赛真题-走方格

按照dfs模板套着套着，写着写着，就出来了

```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int vis[30][30];//标记该点是否被走过
int a[30][30];
int dx[4]={0,1};//方向坐标
int dy[4]={1,0};
int cnt=0;
void dfs(int x,int y){
    if(x==n-1&&y==m-1){//终止条件，到达最后一个格子，坐标为(n-1,m-1)
        cnt++;
        return;
    }
    for(int i=0;i<2;i++){//下一步往哪个方向走(共2个方向)
        int tx=x+dx[i];//下一点的坐标
        int ty=y+dy[i];
        if((tx+1)%2==0&&(ty+1)%2==0)  continue;//行号，列号都为偶数，则跳过
        if(vis[tx][ty]==0&&tx>=0&&tx<n&&ty>=0&&ty<m){//未被访问，且未超出格子
            vis[tx][ty]=1;//标记为访问
            dfs(tx,ty);//从当前坐标继续向后走(递归调用)
            vis[tx][ty]=0;//回溯
        }
    }
}
int main()
{
    cin>>n>>m;
    vis[0][0]=1;//从第一个格子开始，将第一个格子标记为访问过
    dfs(0,0);
    cout<<cnt<<endl;
    return 0;
}
```

动态规划算法：
```cpp
#include<iostream>
using namespace std;
int n,m;
int dp[30][30];
int main()
{
    while(cin>>n>>m)
    {
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
            {
			    if(i == 0 || j == 0){
					dp[i][j] = 1;
					continue;
				}
				if((i + 1) % 2 == 0 && (j + 1) % 2 == 0)  continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];//动态规划转移方程
            }
        cout<<dp[n-1][m-1]<<endl;
    }
    return 0;
}
```

0.0分

7 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

一个人的巴黎

TA的其他文章

你可能喜欢

化学品问题（C语言代码）

2^k进制数（C++代码）使用递归方法

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单编码（C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

蓝桥杯2020年第十一届省赛真题-走方格【DFS/DP】

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

IP判断（C语言代码）

Cylinder （C语言描述，蓝桥杯）

A+B for Input-Output Practice (VI) （C语言代码）

数列排序（C语言代码）

数列有序（C语言代码）

整除的尾数（C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

一个人的巴黎

TA的其他文章

你可能喜欢

化学品问题 （C语言代码）

2^k进制数 （C++代码）使用递归方法

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

简单编码 （C++代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

蓝桥杯2020年第十一届省赛真题-走方格【DFS/DP】

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

IP判断 （C语言代码）

Cylinder （C语言描述，蓝桥杯）

A+B for Input-Output Practice (VI) （C语言代码）

数列排序 （C语言代码）

数列有序 （C语言代码）

整除的尾数 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C++代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

化学品问题（C语言代码）

2^k进制数（C++代码）使用递归方法

简单编码（C++代码）

　　评论区

IP判断（C语言代码）

数列排序（C语言代码）

数列有序（C语言代码）

整除的尾数（C语言代码）