用dist[x1][y1][x2][y2]表示点(x1,y1)到点(x2,y2)的最短距离, 用BFS枚举求得.
枚举所有集合点,
先考虑王和马分别到集合点的距离和.
再考虑王走1步, 枚举其中一只马到去接王, 再到集合点, 其他马各自到集合点的距离.
再考虑王走2步的情形.
/**//*
ID: lorelei
TASK: camelot
LANG: C++
*/
#include <fstream>
#include <memory.h>
#include <queue>
#include <cmath>
using namespace std;
const int N = 40;
const int INF = 9999999;
const int knightx[9]=
{0,-2,-1,1, 2,-2,-1,1,2};
const int knighty[9]={0,-1,-2,-2,-1,1,2, 2,1};
const int kingx1[9]={0,-1,1, 0,0,-1,1,-1,1 };
const int kingy1[9]={0, 0,0,-1,1,-1,-1,1,1};
const int kingx2[16]={0,-1,-2,-2,-2,-2,-2,-1,0,1,2,2,2,2,2,1};
const int kingy2[16]={-2,-2,-2,-1,0,1,2,2,2,2,2,1,0,-1,-2,-2};
typedef struct{
int x,y;
}Point;
int R,C;
int num;
int dist[N][N][N][N];
bool visited[N][N];
Point knights[1000];
Point king;
void BFS(int x, int y){
int i,j;
for(i=1; i<=R; ++i)
for(j=1; j<=C; ++j){
dist[x][y][i][j]=INF;
visited[i][j]=false;
}
queue<Point> Q;
Point temp;
temp.x = x;
temp.y = y;
dist[x][y][x][y]=0;
visited[x][y]=true;
Q.push(temp);
while(!Q.empty()){
temp = Q.front();
Q.pop();
int tx = temp.x;
int ty = temp.y;
for(i=1; i<=8; ++i){
int dx = tx + knightx[i];
int dy = ty + knighty[i];
if(dx>=1&&dx<=R&&dy>=1&&dy<=C&&!visited[dx][dy]){
visited[dx][dy] = true;
dist[x][y][dx][dy] = dist[x][y][tx][ty]+1;
temp.x = dx;
temp.y = dy;
Q.push(temp);
}
}
}
}
inline int max(int a, int b){
return a>b?a:b;
}
int main(){
int i,j,k,t,x;
char ch;
ifstream fin("camelot.in");
ofstream fout("camelot.out");
fin>>R>>C;
fin>>ch>>x;
king.x = x;
king.y = ch-'A'+1;
while(fin>>ch){
num++;
fin>>x;
knights[num].x = x;
knights[num].y = ch-'A'+1;
}
//sovle
for(i=1; i<=R; ++i)
for(j=1; j<=C; ++j)
BFS(i,j);
int ans = INF, sum;
for(i=1; i<=R; ++i)
for(j=1; j<=C; ++j){
sum = 0;
//----------------------------------------------
for(k=1; k<=num; ++k)
sum +=dist[i][j][knights[k].x][knights[k].y];
sum+=max( abs(king.x-i),abs(king.y-j) );
//-----------------------------------------------
int min = INF;
for( t=0; t<=8; ++t){
int tx = king.x + kingx1[t];
int ty = king.y + kingy1[t];
if(tx>=1 && tx<=R && ty>=1 && ty<= C){
for(k=1; k<=num; ++k){
int cur = dist[knights[k].x][knights[k].y][tx][ty] + dist[tx][ty][i][j] -
(dist[i][j][knights[k].x][knights[k].y] + max( abs(king.x-i),abs(king.y-j) ) );
if(t!=0)
cur++;
if(cur<0 && cur<min)
min = cur;
}
}
}
for( t=0; t<16; ++t){
int tx = king.x + kingx2[t];
int ty = king.y + kingy2[t];
if(tx>=1 && tx<=R && ty>=1 && ty<= C){
for(k=1; k<=num; ++k){
int cur = dist[knights[k].x][knights[k].y][tx][ty] + dist[tx][ty][i][j] +2 -
(dist[i][j][knights[k].x][knights[k].y] + max( abs(king.x-i),abs(king.y-j) ) );
if(cur<0 && cur<min)
min = cur;
}
}
}
if(min!=INF&&min<0)
sum += min;
if(sum<ans)
ans = sum;
}
if(R==0 || C==0)
fout<<0<<endl;
else
fout<<ans<<endl;
return 0;
}
posted on 2011-01-13 00:31
小阮 阅读(707)
评论(0) 编辑 收藏 引用 所属分类:
USACO