洛谷P1002——过河卒
2024-08-23 15:16:05
又是洛谷题,要不是有小姐姐不会,我才不想动脑子。先贴一下题目地址https://www.luogu.org/problem/P1002
再贴一下题目:
我们读一下题目,这可不比学校的**算法题,读完一遍没啥感觉。我意识到需要画图了,(噢,我垃圾的画图技术)
因为卒只能向下或者向右,也就是说,除了第一行第一列之外,当前索引上的元素的值都仅由其上方元素与前方元素共同决定。(图中5,6写错应该是1)
A表示卒所在的地方, B表示目的地,M表示马,红色的坐标表示封锁区,格子里的数字表示走到该位置有多少方法。现在我们可以轻易的从图中轻易的发现 Map[i,j] = Map[i-1, j] + Map[i, j-1]; 所以我们可以很轻松的得出状态转移方程
Map[1][1] = 1;
Map[i][j] = MAX(Map[i-1][j]+Map[i][j-1]);//c语言里没有MAX自己写一个去
针对没有MAX又不想写的我,我略微改动了一下状态方程:
Map[1][0] = 1;
Map[i][j] = Map[i-1][j]+Map[i][j-1];
利用了一下空出来的0列,为什么要空出0行和0列呢?因为这个方程Map[i-1][j]+Map[i][j-1] 取到0会产生数组越界然后就RE
顺便说一下为了避免数组越界所以我把输入的数据全部+1,这样就避免了内存泄漏,这道题还专门说明了数据会很大,所以应该用longlong。解决了这几点之后我们就可以写代码了
巴拉巴拉~
贴代码:
#include <stdio.h>
#include <stdbool.h>
#define DEBUG 0
#define Format \
Bx++; \
By++; \
Hx++; \
Hy++; \
map[][] = ; \
H_map[Hx][Hy] = ;
typedef long long ll;
typedef unsigned char uchar; ll map[][] = {};
bool H_map[][] = {};
//限制点
const int Hforbidx[] = {, -, -, , , , , -, -};
const int Hforbidy[] = {, , , , , -, -, -, -}; int main()
{
int Bx, By, Hx, Hy; scanf("%d%d%d%d", &Bx, &By, &Hx, &Hy);
//初始化
Format; //标志点
for (int i = ; i <= ; i++)
{
H_map[Hx + Hforbidx[i]][Hy + Hforbidy[i]] = ;
//测试点1
#if DEBUG
printf("i = %d j = %d\n", Hx + Hforbidx[i], Hy + Hforbidy[i]);
#endif
} for (int i = ; i <= Bx; i++)
{
for (int j = ; j <= By; j++)
{
if (H_map[i][j])
{
//测试点2
#if DEBUG
printf("\n%d\n", H_map[i][j]);
#endif // DEBUG
map[i][j] = ; //被马拦住了记住清零
continue;
}
//状态转移方程
map[i][j] = map[i - ][j] + map[i][j - ];
//测试点2
#if DEBUG
printf("map[%d][%d] = %d\n", i, j, map[i][j]);
if ( == j % )
{
putchar('\n');
}
#endif // DEBUG
}
}
printf("%lld\n", map[Bx][By]); return ;
}
切记,自己先写。
最新文章
- 关于容器为NavigationControlle时,view的起始位置的问题
- Docker-3:Data Volume
- 【C#】1.3 WPF应用程序学习要点
- atomic vs. nonatomic
- json2form已改名为AForm
- 用minicom 产看 usb的串口
- MyEclipse 下用link 方式安装插件
- [置顶] 数据持久层(DAO)常用功能–通用API的实现
- mysql中的意向锁IS,IX
- linux中的strings命令简介2
- C#代码生成工具:文本模板初体验 使用T4批量修改实体框架(Entity Framework)的类名
- 英语app分析
- SLAM+语音机器人DIY系列:(三)感知与大脑——1.ydlidar-x4激光雷达
- spring boot 2.0 neo4j 使用
- 入侵感知系列之webshell检测思路
- Mysql MHA高可用集群架构
- mobilenet之Depthwise +Pointwise
- vba 调用 countif 函数问题
- PHP引用赋值
- C#实现Google S2算法