题目链接 http://train.usaco.org/usacoprob2?a=6qnm38cEkwF&S=camelot
题目大意：在一个最大为30行26列的国际象棋盘里，放1个王和若干个骑士，骑士最多可以铺满棋盘。初始状态没有棋子在同一个格子。在走若干步之后，若骑士和王在同一个格子，王可以跟随骑士一起走（上马），上马不算一步。问最少多少步后所有棋子在同一个格子。王和骑士的行走方式如图：
骑士.png
王.png
对于这一题，刚开始我是无从下手。既不知道哪个骑士在哪个点接王，也不知道最终在哪个点汇聚，只是直觉上觉得是最短路问题。在我的一个大佬同学介绍了他的做法后，我才有了思路，在他的基础上，使用了另一种方法，类似spfa中的松弛操作来寻找最短路。下面介绍我的做法。
首先，如果没有王的存在，仅仅让若干个骑士在某个点汇聚，求最少步数，这就是个很直接的广搜问题，求每个骑士到每个点的最少步数，枚举每个点求和，取和最小的那个点。
那加上王之后呢？很容易想到的就是贪心，但这正是这题的一个注意点：不能因为王走的慢，骑士走的快而贪心的认为骑士要在距离王很近的地方接王。反例有大佬已经给出http://www.yuxuandong.com/post/usaco37.html
因此不放换一种思路，让王来找骑士，而非骑士找王（这句话是思路的关键）。不管是我的做法，还是给我启发的那种做法，都是以这句话为前提。
先来介绍一下同学的做法：
对于每个骑士，定义一个结构体，如果没有王，结构体中无非就是坐标和距离。加上王之后，其实加上一个bool值就可以，判断骑士到这一点是否带上王。结构体定义大致如下：
struct Knight
{
int x,y;
int dis;
bool king;//表示骑士在(x,y)位置是否带上王
};
所以在广搜的时候，就根据队首的king值为TRUE或FALSE更新八个邻接点，也即带王的队列比不带王的队列大一倍。
下面介绍一下我的做法：
我的思路也是这种思路，只是在处理的时候采用了类似spfa松弛操作的方法进行广搜，骑士的结构体定义如下
struct Knight
{
int r,c;
int dis,kdis; //dis为骑士到(r,c)不带王的最少步数，kdis为骑士到(r,c)带上王的最少步数
};
在广搜的时候，以每个骑士初始位置进行一次广搜，即找每个骑士到每个点带王和不带王的最少步数。我定义了一个三维数组（为什么是三维后面会解释），Knight dist[800][31][28]，其中第一维表示是哪个骑士，后两维表示棋盘上每个点。在广搜的时候，设骑士初始位置start，对于队首qf的每个邻接点adj，如果dis(start,qf)+dis(start,adj)<dis(start,adj)，就更新dis(start,adj)，并且若adj不在队列中，就将邻接点入队。看到这里，大家应该都看出来了，就是spfa。关键问题是，dis好更新，那kdis呢？似乎不怎么好求。我先把代码贴出来，然后解释一下我的做法。
void bfs(Knight& s,int pos)
{
int vis[31][31];
for(int i=0;i<31;i++)
{
for(int j=0;j<31;j++)
{
dist[pos][i][j].dis=IM;
dist[pos][i][j].kdis=IM;
vis[i][j]=0;
}
}
queue<Knight> q;
vis[s.r][s.c]=1;
dist[pos][s.r][s.c].dis=0;
dist[pos][s.r][s.c].kdis=getdis(s.r,s.c);
q.push(s);
while(!q.empty())
{
Knight temp=q.front();
q.pop();
vis[temp.r][temp.c]=0;
for(int i=0;i<8;i++)
{
Knight nxt;
if(judge(temp.r+dx[i],temp.c+dy[i]))
{
nxt.r=temp.r+dx[i];nxt.c=temp.c+dy[i];
nxt.dis=dist[pos][temp.r][temp.c].dis+1;
nxt.kdis=min(getdis(nxt.r,nxt.c)+dist[pos][temp.r][temp.c].dis+1,dist[pos][temp.r][temp.c].kdis+1);
if(nxt.dis<=dist[pos][nxt.r][nxt.c].dis&&nxt.kdis<=dist[pos][nxt.r][nxt.c].kdis)
{
dist[pos][nxt.r][nxt.c].dis=nxt.dis;
dist[pos][nxt.r][nxt.c].kdis=nxt.kdis;
if(!vis[nxt.r][nxt.c])
{
q.push(nxt);
vis[nxt.r][nxt.c]=1;
}
}
}
}
}
int getdis(int r,int c)//求王到(r,c)的最少步数
{
return min(abs(kingr-r),abs(kingc-c))+abs(kingr-r-kingc+c);
}
因为王每次只能向周围八个格子中任意一个走一格，所以王到任意一格的最少步数O(1)时间就能求出，见上面getdis函数。因此对于队首的每一个邻接点，其kdis只可能是两种情况：在队首就带上王，走一步到当前点（dist[pos][temp.r][temp.c].kdis+1）和在到当前点之前都不带王，到当前点王过来（getdis(nxt.r,nxt.c)+dist[pos][temp.r][temp.c].dis+1）。
在对每个骑士都广搜一次之后，就要枚举点作为最终汇聚点，求最少步数。在求和的时候我也做了一些优化：只有一个骑士要带王，所以我循环一次，求每个骑士到当前点的步数之和的同时，顺带求每个骑士的kdis和dis的差的最小值，所以对于当前点作为终点的最少步数就是所有骑士的dis之和加kdis和dis的差的最小值。
//枚举终点
for(int i=1;i<=row;i++)
{
for(int j=1;j<=col;j++)
{
int tempres=0;
int cha=IM;
for(int k=0;k<knt.size();k++)
{
if(dist[k][i][j].dis==IM) continue;
tempres+=dist[k][i][j].dis;
cha=min(cha,dist[k][i][j].kdis-dist[k][i][j].dis);
}
tempres+=cha;
res=min(res,tempres);
}
}
此处解释一下为什么要用三维数组，其实无非就是空间换时间，如果不用三维数组记录每个骑士到每个点的最少步数，那么枚举终点的时候，都要对每个骑士广搜一次，显然超时，而非像现在一样，只需广搜一次。
最后稍微总结一下：
本题的关键就是要明确让王来找骑士，而非骑士接王。再有就是要考虑如何在广搜的时候确定骑士带上王的最少步数。
附AC代码：
#include<iostream>
#include<fstream>
#include<string>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
int row,col;
int kingr,kingc;
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={-1,1,-2,2,-2,2,-1,1};
struct Knight
{
int r,c;
int dis,kdis;
};
const int IM=(1<<30);
int res=IM;
vector<Knight> knt;
int getdis(int ,int);
void bfs(Knight&,int);
bool judge(int,int);
Knight dist[800][31][28];
int main()
{
ofstream fout("camelot.out");
ifstream fin("camelot.in");
fin>>row>>col;
char c;
fin>>c>>kingr;
kingc=c-'A'+1;
while(fin>>c)
{
int kr,kc;
if(c>'Z'||c<'A') continue;
kc=c-'A'+1;
fin>>kr;
Knight k;
k.r=kr;k.c=kc;
k.dis=IM;k.kdis=IM;
knt.push_back(k);
}
if(knt.size()==0)
{
fout<<0<<endl;
return 0;
}
for(int k=0;k<knt.size();k++)
{
bfs(knt[k],k);
}
//枚举终点
for(int i=1;i<=row;i++)
{
for(int j=1;j<=col;j++)
{
int tempres=0;
int cha=IM;
for(int k=0;k<knt.size();k++)
{
if(dist[k][i][j].dis==IM) continue;
tempres+=dist[k][i][j].dis;
cha=min(cha,dist[k][i][j].kdis-dist[k][i][j].dis);
}
tempres+=cha;
res=min(res,tempres);
}
}
fout<<res<<endl;
return 0;
}
void bfs(Knight& s,int pos)
{
int vis[31][31];
for(int i=0;i<31;i++)
{
for(int j=0;j<31;j++)
{
dist[pos][i][j].dis=IM;
dist[pos][i][j].kdis=IM;
vis[i][j]=0;
}
}
queue<Knight> q;
vis[s.r][s.c]=1;
dist[pos][s.r][s.c].dis=0;
dist[pos][s.r][s.c].kdis=getdis(s.r,s.c);
q.push(s);
while(!q.empty())
{
Knight temp=q.front();
q.pop();
vis[temp.r][temp.c]=0;
for(int i=0;i<8;i++)
{
Knight nxt;
if(judge(temp.r+dx[i],temp.c+dy[i]))
{
nxt.r=temp.r+dx[i];nxt.c=temp.c+dy[i];
nxt.dis=dist[pos][temp.r][temp.c].dis+1;
nxt.kdis=min(getdis(nxt.r,nxt.c)+dist[pos][temp.r][temp.c].dis+1,dist[pos][temp.r][temp.c].kdis+1);
if(nxt.dis<=dist[pos][nxt.r][nxt.c].dis&&nxt.kdis<=dist[pos][nxt.r][nxt.c].kdis)
{
dist[pos][nxt.r][nxt.c].dis=nxt.dis;
dist[pos][nxt.r][nxt.c].kdis=nxt.kdis;
if(!vis[nxt.r][nxt.c])
{
q.push(nxt);
vis[nxt.r][nxt.c]=1;
}
}
}
}
}
}
int getdis(int r,int c)
{
return min(abs(kingr-r),abs(kingc-c))+abs(kingr-r-kingc+c);
}
bool judge(int x,int y)
{
return x>=1&&x<=row&&y>=1&&y<=col;
}
网友评论