技术标签： output input 测试 动态规划 bfs
3 1 2 3 1 2 3 1 2 3 3 1 1 1 1 1 1 1 1 1
1 6
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct point {
int x;
int y;
};
int direction[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int distances[51][51];//distances[i][j]表示该点到终点的最小距离
int map[51][51];//map[i][j]表示经过该点的时间
__int64 sum[51][51];//sum[i][j]表示该点到终点的路线总数
int n;
//bfs找出各点到终点的最小距离
void bfs(void) {
point current;
current.x = n - 1;//当前位置
current.y = n - 1;
distances[n - 1][n - 1] = map[n - 1][n - 1];
queue<point>Queue;//建立队列
Queue.push(current);
while (!Queue.empty()) {//当队列非空
current = Queue.front();//头结点出队列
Queue.pop();
point next;
for (int i = 0; i < 4; i++) {
next.x = current.x + direction[i][0];
next.y = current.y + direction[i][1];
if (next.x >= 0 && next.y >= 0 && next.x < n && next.y < n)
if (distances[next.x][next.y] > distances[current.x][current.y] + map[next.x][next.y]) {
distances[next.x][next.y] = distances[current.x][current.y] + map[next.x][next.y];
Queue.push(next);//如果节点满足条件则入队列
}
}
}
}
//dp求出各点到终点的路线总数
__int64 dp(int x,int y){
if(x==n-1&&y==n-1)//如果(x,y)是终点，返回1
return 1;
if(sum[x][y])//该点进行过dp，直接返回
return sum[x][y];
for(int i=0;i<4;i++){
int x2=x+direction[i][0];
int y2=y+direction[i][1];
if(x2>=0&&y2>=0&&x2<n&&y2<n&&distances[x2][y2]<distances[x][y])
sum[x][y]+=dp(x2,y2);
}
return sum[x][y];
}
int main(void) {
while (scanf("%d", &n) != EOF) {
memset(sum,0,sizeof(sum));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
scanf("%d", &map[i][j]);
distances[i][j] = INT_MAX;
}
bfs();
printf("%I64d\n",dp(0,0));
}
return 0;
}
0x01基本信息地址：https://hackmyvm.eu/machines/machine.php?vm=Warez靶机ip：192.168.181.159keli IP：192.168.181.1290x02实施过程首先进行ip扫描于是打开网页进行查看于是我进行目录扫描gobuster dir -u http://192.168.181.159/ -w /usr/share/wordlists/dirbuster/directory-list-2.3-me..
云服务器安卓多开 内容精选换一换Linux云服务器常用的登录方式是SSH，对于密码登录方式创建的云服务器，如何保证登录安全性呢？本文以CentOS 7.6为例，对SSH登录进行安全加固。通过SSH密码方式远程登录云服务器。执行以下命令，修改SSH登录的默认端口，比如修改为“5000”。vim /etc/ssh/sshd_config按“i”进入编辑模式，在第17行，将注按需计费：按需计费是后付费模...
最近看到温绍锦的JVM基础，里面看到这个jar hell问题的解决方法，之前遇到过一次，是一个资源文件，当时觉得挺麻烦，不知道还有这个方法，很棒，特地整理了下，记录到这里来，这个博客开了好长时间了，一直以来也懒得写东西，以后会坚持更新些。ClassLoader classLoader = Thread.currentThread().getContextClassLoader(); St
CCF CSP 数列分段解题报告
5、Which two affect the time taken for instance recovery? A) size of redo logs B) size of UNDO tablespace C) FAST_START_MTTR_TARGET value D) siz...
本文详细介绍Linux内核: 修改TCP/IP调优参数 所有的TCP/IP调优参数都位于/proc/sys/net/目录. 例如, 下面是最重要的一些调优参数, 后面是它们的含义: 1. /proc/sys/net/core/rmem_max — 最大的TCP数据接收缓冲 2. /proc/sys/net/core/wmem_max — 最大的TCP
数据库结构与模式数据库管理系统的类型通常有多个分类标准。如按数据模型分类、按用户数分类、按数据库分布站点分类等。但我们需要了解的，主要还是按数据模型分类。目前常见的 DBMS 按数据模型划分，包括：关系型 DBMS、文档型 DBMS、键值型 DBMS、对象型 DBMS 等。三级抽象数据库系统划分为三个抽象级：用户级、概念级、物理级。 （1）用户级数据库。用户级数据库对应于外模式...
介绍奇偶校验码、海明码 （1）奇校验：就是让原有数据序列中（包括你要加上的一位）1的个数为奇数1000110（0）你必须添0这样原来有3个1已经是奇数了所以你添上0之后1的个数还是奇数个。（2）偶校验：就是让原有数据序列中（包括你要加上的一位）1的个数为偶数1000110（1）你就必须加1了这样原来有3个1要想1的个数为偶数就只能添1了。（3）奇偶校验码的用途 ①奇偶校验是用来检查数据传输的正确性的方法。奇偶校验能检测出传输数据的部分错误（1位误码能检测出
Docker在window上安装默认是支持window10系统的，对于window7系统的用户安装就要费一点功夫了，笔者按当前（2020年3月22日）最新的版本来写一下安装步骤：1、在window7上安装Docker首先要下载DockerToolbox，Docker Toolbox提供了一种在不满足Docker Desktop for Windows应用最低系统要求的Windows系统上使用Docker的方法。下载地址传送门：https://github.com/docker/toolbox/relea
来源| 广告猎人 微信号| i4AADS说到借势文案，不得不服杜蕾斯。往年的感恩节，杜蕾斯的文案足够精彩。今年更有意思，杜蕾斯放了个大招，一口气调戏了十几个品牌。每小时推送一张海报，从上午10点开始，一直持续到晚上10点。非常持久，看得非常过瘾。从昨天上午十点开始直到晚上十点结束杜杜每隔一小时发布一张
Windows严重漏洞，请大家开启自动更新或手工下载安装补丁。Windows 7 x86:http://download.windowsupdate.com/d/msdownload/update/software/secu/2019/05/windows6.1-kb4499175-x86_6f1319c32d5bc4caf2058ae8ff40789ab10bf41b.msuWindows 7 x64:http://download.windowsupdate.com/d/msdownload/up
马云曾说：把事情要做到，一般来说靠男性；但是把事情要做好，一定得靠女性；把事情做妙，那得男女一起干。男人不管多厉害，离开了女性，他们啥都不是。只有女性好，世界才会好。没有女性，就不可能有阿里巴巴。是女性带给了阿里巴巴成功的机会，是女性的信任，让阿里与众不同。如马云所言，在阿里成立起初有一半员工是女性。一直以来，女性在公司中扮演着至关重要的角色。比如阿里「十八罗汉」中的：张瑛、彭蕾、戴珊、蒋芳。此外，在阿里现任高管团队中，首席财务官武卫、首席人才官童文红、首席客户服务官吴敏芝都是非常知名的女性高管。相