usaco Camelot_silence401的博客-程序员信息网

技术标签: usaco  


 被这道BFS不带权图的最短路水题卡了三天,提交了80次。。。。。。就这样弱成渣了。。。。。。。。
  这道题其实思路很简单,先求出每个点到所有点的最短路,然后枚举集合点,枚举接国王的骑士,枚举接国王的点,算出需要的距离。
    总距离=Min{所有骑士到集合点的距离和-接国王的骑士到集合点的距离+国王到骑士接他的点的距离+骑士到接国王点的距离+其实从接国王的点走到集合点的距离}    (当然太朴素就铁定超时了)
  然后开始处理各个细节。
  首先求最短路,一开始脑子没动当然就想到用Dijkstra求(我有多沙茶。。。),当然O(v*v^2)铁定要超时啊,所以用heap+Dijkstra做了一下。。。果然还是超时。。。这时候我终于缓过神来,这是无权图啊!求无权图的最短路就从每一个点开始走一遍BFS就出来了啊!。。。
  然后是枚举的问题,朴素枚举当然O(n^3)超时,然后观察到这个图最大是30*26,然后估计一下最远的骑士和国王,估算后发现接国王的点应该在国王周围5格内,(这题数据弱,2格内就可以AC了,或者2格是对的?)。然后就胡乱AC了。。。

这是网上一大神的思路




这题对我来说最大的收获就是知道memset(a,0x3f,sizeof(a))a的初值为十位数然而memset(a,10,sizeof(a))a的初值为9位数。

/*
ID:jinbo wu
LANG:C++
TASK:camelot
*/
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int d[8][2]={
   {-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
struct node
{
	int x,y;
}kn[1000];
node king;
int r,c;
int dist[40][30][40][30];
bool vis[40][30];
int kdist[40][30];
int allk[40][30];
queue<pair<int,int> > q;
void bfs(int x,int y)
{
	memset(vis,0,sizeof(vis));
    vis[x][y]=1;
    dist[x][y][x][y]=0;
    q.push(make_pair(x,y));
    while(!q.empty())
    {
    	int kx=q.front().first;
    	int ky=q.front().second;
    	q.pop();
    	for(int i=0;i<8;i++)
    	{
    		int dx=kx+d[i][0];
    		int dy=ky+d[i][1];
    		if(dx>=0&&dx<r&&dy>=0&&dy<c&&!vis[dx][dy])
    		{
    			dist[x][y][dx][dy]=dist[x][y][kx][ky]+1;
    			vis[dx][dy]=1;
    			q.push(make_pair(dx,dy));
    		}
    	}
    }
    return ;

}
int main()
{
  freopen("camelot.in","r",stdin);
  freopen("camelot.out","w",stdout);
  char a;
  int b;
  cin>>r>>c;
  cin>>a>>b;
  king.y=a-'A';
  king.x=b-1;
  int num=0;
  while(cin>>a>>b)
  {
  	kn[num].y=a-'A';
  	kn[num++].x=b-1;
  }
  memset(dist,10,sizeof(dist));
  for(int i=0;i<r;i++)
  	for(int j=0;j<c;j++)
  		bfs(i,j);
  	for(int i=0;i<r;i++)
  		for(int j=0;j<c;j++)
  			kdist[i][j]=max(abs(king.x-i),abs(king.y-j));
  for(int i=0;i<r;i++)
  	for(int j=0;j<c;j++)
  		for(int k=0;k<num;k++)
  			allk[i][j]+=dist[i][j][kn[k].x][kn[k].y];
  		int ans=INF;
  		if(!num)
  		{
  			for(int i=0;i<r;i++)
  				for(int j=0;j<c;j++)
  					ans=min(ans,kdist[i][j]);
  		}
  		else
  		{
  			for(int k=0;k<num;k++)
  			{
  				for(int i=king.x-2;i<king.x+2;i++)
  					for(int j=king.y-2;j<king.y+2;j++)
  						if(i>=0&&i<r&&j>=0&&j<c)
  						{
                              for(int n=0;n<r;n++)
                              	for(int m=0;m<c;m++)
                              		ans=min(ans,abs(allk[n][m]-dist[kn[k].x][kn[k].y][n][m]+dist[kn[k].x][kn[k].y][i][j]+kdist[i][j]+dist[i][j][n][m]));
  						}
  			}
  		}
  		cout<<ans<<endl;
}




版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/silence401/article/details/53616136

智能推荐

blockQueue阻塞队列_菜菜思密达的博客-程序员信息网_blockqueuesize

阻塞队列的实现ArrayBlockingQueue 实现了BlockingQueue接口,主要的变量是 /* * Concurrency control uses the classic two-condition algorithm * found in any textbook. */ /** Main lock guarding all access */ final ReentrantLock lock; /** Condition

很不错的jQuery学习资料和实例,分享给大家。_iteye_3762的博客-程序员信息网

这些都是学习Jquery很不错的资料,整理了一下,分享给大家。 希望能对大家的学习有帮助。帕兰 Noupe带来的51个最佳jQuery教程和实例, 向大家介绍了jQuery的一些基本概念和使用的相关教程, 如果你对jQuery感兴趣, 也可以查看帕兰写的文章: 37个更加出色的jQuery插件 45个新鲜出炉的jQuery插件 50多个强大的jQ...

flutter开发 error: Target of URI doesn't exist: 'package:xxx.dart 引用内部文件出错_淡淡的时光的博客-程序员信息网

如果你的编码没有任何问题的话,但是import 引用出现红线报错,原因可能是你的文件编码格式不一致,比如有的是GBK有的是UTF-8

序列化--Serializable与Parcelable_weixin_33725272的博客-程序员信息网

前言:序列化:就是将对象的状态信息转换为可以存储或传输的形式的过程在我们平时开发中.我们用到序列化最多的地方就是通过intent传递对象,如果你要在intent中传递基本数据类型以外的对象,那么该对象必须实现Serializable或者Parcelable,否则会报错注意:1:通过intent传递过去的对象是经过了序列化与反序列化的,虽然传送的对象和接收的对象内容相同,但是是不同的对象,...

python中如何连接两个字符串_Python中字符串拼接的N种方法_weixin_39968861的博客-程序员信息网

python拼接字符串一般有以下几种方法:①直接通过(+)操作符拼接s = 'Hello'+' '+'World'+'!'print(s)输出结果:Hello World!使用这种方式进行字符串连接的操作效率低下,因为python中使用 + 拼接两个字符串时会生成一个新的字符串,生成新的字符串就需要重新申请内存,当拼接字符串较多时自然会影响效率。②通过str.join()方法拼接strlist=[...

随便推点

akoj-1170-国王的魔镜_jtahstu的博客-程序员信息网

国王的魔镜Time Limit:1000MS  Memory Limit:65536KTotal Submit:43 Accepted:21Description国王有一个魔镜,可以把任何接触镜面的东西变成原来的两倍——只是,因为是镜子嘛,增加的那部分是反的。 比如一条项链,我们用AB来表示,不同的字母表示不同颜色的珍珠。如果把B端接触镜面的话,魔镜会把这条项链变为ABBA。如

静态方法泛型_老头儿ii的博客-程序员信息网_android 静态方法泛型

静态方法泛型定义&lt;T&gt;只能放在static关键字之后

前端H5可视化拖拽布局器-Layui,Bootstrap等各种UI-可视化表单设计器_程序类猿的博客-程序员信息网_h5可视化拖拽生成工具

本节介绍一款前端H5可视化布局器 MagicalDrag2.1.5 由js+css+html编写而成软件官方在线使用地址:http://layuiout.magicalcoder.com/layui在线使用:免费优点在于 功能强大,可以自由嵌入各种web项目,有html+css+js编写而成,可以基于各种设备响应式设计布局软件基本截图主界面 (图片拉扯了好难看)各种下拉编辑...

C Primer Plus (第六版) 第十三章_编程练习答案_LandY和C的博客-程序员信息网

no1.c// 修改程序清单13.1中的程序,要求提示用户输入文件名,并读取用户输入信息,不使用命令行参数.# include &lt;stdio.h&gt;# include &lt;stdlib.h&gt;int main(void){ int ch ; FILE * fp ; char st[100]; unsigned long count = 0 ; prin...

PELCO-D协议 要点整理_lk989898的博客-程序员信息网_pelco-d

消息格式:Byte 1 Byte 2 Byte 3 Byte 4 Byte 5 Byte 6 Byte 7 Sync Byte Address Command 1 Command 2 Data 1 Data 2 Checksum The synchronization byte (Sync Byte) is...

Android 11 允许安装未知来源权限 变动_高凤森的博客-程序员信息网_android 未知来源权限

Android 11 允许安装未知来源权限 变动一、部分机型兼容问题最近在为Flutter端封装 下载apk并安装 的功能,众所周知,在安装之前我们要请求 ‘允许安装未知来源’ 这个权限,然后我就写了以下代码(部分代码)if (Build.VERSION.SDK_INT &gt;= Build.VERSION_CODES.O) { val isHasPermission = activity.packageManager?.canRequestPackageInstalls() ?: false

推荐文章

热门文章

相关标签