小哈哈

用户名：20180390139

访问量：19775

签　名：

世界上怎么会有那么聪明的人呢？

等　　级
排　　名	216
经　　验	6373
参赛次数	9
文章发表	38
年　　龄	0
在职情况	学生
学　　校	蓝翔挖掘机技校
专　　业	网络工程

　　自我简介：

我是个傻嗨，但是我会努力像个正常人

TA的其他文章

蓝桥杯2013年第四届真题-大臣的旅费-题解(C++代码)--------------------重点是这个结论，知道后就很简单了
浏览：399

蓝桥杯2015年第六届真题-赢球票-题解(C++代码)-------------队列的出队入队，很简单的
浏览：342

你可能喜欢

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

水陆距离 -题解(C语言代码)---------动态规划，简单求解

　　作者: 小哈哈　　　　发表时间：2019-09-01 18:45:03 浏览：955　|　评论：1　

原题链接：水陆距离

##########别看我代码长，关键代码就几条#######
##A
这道题如果用搜索的话，估计会时间超限，所以就采用动态规划的做法，
主要的想法是，我要知道（i,j)这个点离最近的水域的距离为多少，如果我已经知道
（i+1,j)（i-1,j)（i,j+1)（i,j-1)这4个点离最近的水域的距离为多少那就好了，哪怕只知道一个也行。因为这4个点都是（i,j)位置  周围的点

#1、
所以动态规划的 第一步状态已经大概清楚了
   也就是我想用dp[i][j]表示什么，这里我们就用dp[i][j]表示（i,j)这个点离最近的水域的距离，
#2、
然后动态规划的第二步，写状态转移方程：
 dp[i][j]=min(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1])+1;

这条式子表示的是：我要知道（i,j)这个点离最近的水域的距离为多少，如果我已经知道（i+1,j)（i-1,j)（i,j+1)（i,j-1)这4个点离最近的水域的距离为多少那就好了，哪怕只知道一个也行。然后比较他们的值，就取最小那个，然后加1，因为这4个点都是（i,j)位置  周围的点，这几个点只要走一步就可以到（i,j)这个位置了
	#include<stdio.h>
    #define N 200
    #define MAX 999999  //表示正无穷
    int min(int a,int b,int c,int d);  //返回4个数的最小的那个
    int n,m,A[N][N]={0},dp[N][N]={0};
    char s[N];
    int main(){
    	int i,j,sum=0;
    	scanf("%d%d",&n,&m);
    	for(i=0;i<n;i++){
    		scanf("%s",s);//题目的数据样例都是字符串，所以下面要转换成数字
    		j=0;
    		while(s[j]!='\0'){
    			A[i+1][j+1]=s[j]+0-'0';
    			j++;
    		};
    	}
    	for(i=1;i<=n;i++){
    		for(j=1;j<=m;j++){
    			
    			if(A[i][j]==0)
    		dp[i][j]=0;//如果这个点是水域，那它到水域的距离肯定为0
    			else
    		dp[i][j]=MAX;//如果这个点不是水域，那先让它到水域的距离为正无穷
    		}
    	}
    	for(i=0;i<=m;i++)
    		dp[0][i]=MAX;
    	for(j=0;j<=n;j++)
    		dp[j][0]=MAX;
    	for(i=0;i<=m+1;i++)
    		dp[n+1][i]=MAX;
    	for(j=0;j<=n+1;j++)
    		dp[j][m+1]=MAX;
    /*上面是让我们输入的地图的周围  的dp[i][j]的值为正无穷，因为这条式子
    dp[i][j]=min(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1])+1;
	比如dp[1][1]=min(dp[0][1],dp[2][1],dp[1][0],dp[1][2])
	dp[0][1]表示的是（0，1）这个位置距离最近水域的距离，但是（0，1）压根不在我们输入的地图上，也就是它不是我们地图上的点，所以上面是4个循环不能少*/
#####下面才是关键的代码
    	while(sum<m*n){//这个动态规划有点不一样的地方是，循环一次还不能让所有的dp[i][j]的值为最优解，所以循环多几次咯
    
    	for(i=1;i<=n;i++){
    		for(j=1;j<=m;j++){
    
    			if(A[i][j]==1)
    				dp[i][j]=min(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1])+1;//这个状态转移方程前面说了
    			
    		}
    	}
    
    	sum++;
    
    	};
    	
    
    	for(i=1;i<=n;i++){
    		for(j=1;j<=m;j++){
    			printf("%d ",dp[i][j]);
    		}
    		printf("\n");
    	}
    
    
    	return 0;
    	
    }
    
    int min(int a,int b,int c,int d){
    
    	int e=MAX;
    	e=a>e ? e:a;
    	e=b>e ? e:b;
    	e=c>e ? e:c;
    	e=d>e ? e:d;
    	return e;
    }

0.0分

17 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

　　评论区

jcnet

怎么确定循环多少次可以得到最优解？是否有必要循环m*n次呢？

2021-05-17 13:20:43

小哈哈

TA的其他文章

你可能喜欢

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

不需要数组和指针的做法！！！

Lucky Word （C++代码）

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

水陆距离 -题解(C语言代码)---------动态规划，简单求解

评论区

精彩推荐

【回文数(二)】（C语言代码）

简单的a+b （C语言代码）

printf基础练习2 （C语言代码）

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

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

剪刀石头布（C语言代码）

WU-链表数据求和操作（C++代码）

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

字符逆序（C语言代码）

【偶数求和】（C语言代码）

小哈哈

TA的其他文章

你可能喜欢

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

不需要数组和指针的做法！！！

Lucky Word （C++代码）

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

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

水陆距离 -题解(C语言代码)---------动态规划，简单求解

评论区

精彩推荐

【回文数(二)】 （C语言代码）

简单的a+b （C语言代码）

printf基础练习2 （C语言代码）

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

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

剪刀石头布 （C语言代码）

WU-链表数据求和操作 （C++代码）

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

字符逆序 （C语言代码）

【偶数求和】 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

　　评论区

【回文数(二)】（C语言代码）

剪刀石头布（C语言代码）

WU-链表数据求和操作（C++代码）

字符逆序（C语言代码）

【偶数求和】（C语言代码）