USACO camelot 好题
这道题的意思是地图上有一些骑士和一个国王， 骑士和国王要在一点会和，你可以选择一个骑士和国王在一点会和然后骑士会带着国王继续走， 问他们汇合的最少步数和是多少？考虑一个骑士当没有国王的时候可以很容易的求出他到每个点的最短路径a， 现在他要带着国王， 那么我们可以计算出他带着国王到某一点的最短路径b, 那么为了接国王他多走的路就是b - a,这下我们可以维护两个数组， cost[i][j]表示所有骑士不接国王到达i, j所需要的最短的步数， kcost[i][j]表示有一个骑士接国王到i,j，骑士多走的步数（也包括国王走的步数），那么答案就是min(cost[i][j]+kcost[i][j]),代码如下：
/* ID: m1500293 LANG: C++ PROG: camelot */ #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; int N, M; int kx, ky; int cost[35][35], kingcost[35][35]; int kcost[35][35]; int dis[35][35][2]; int dx[] = {-2, -2, -1, -1, +1, +1, +2, +2}; int dy[] = {-1, +1, -2, +2, -2, +2, -1, +1}; bool inside(int x, int y) { return (x>=0&&x<N&&y>=0&&y<M); } struct State { int x, y, flog; State() {} State(int x, int y, int flog):x(x), y(y), flog(flog) {} }; int inque[35][35][2]; void bfs(int knx, int kny) { memset(inque, 0, sizeof(inque)); memset(dis, 0x3f, sizeof(dis)); queue<State> que; dis[knx][kny][0] = 0; inque[knx][kny][0] = 1; que.push(State(knx, kny, 0)); while(!que.empty()) { State u = que.front(); que.pop(); inque[u.x][u.y][u.flog] = 0; int udis = dis[u.x][u.y][u.flog]; for(int i=0; i<8; i++) { int nx = u.x+dx[i], ny = u.y+dy[i]; if(!inside(nx, ny)) continue; if(dis[nx][ny][u.flog] > udis + 1) { dis[nx][ny][u.flog] = udis+1; if(!inque[nx][ny][u.flog]) { inque[nx][ny][u.flog] = 1; que.push(State(nx, ny, u.flog)); } } } if(!u.flog && dis[u.x][u.y][1]>udis + kingcost[u.x][u.y]) { dis[u.x][u.y][1] = udis+kingcost[u.x][u.y]; if(!inque[u.x][u.y][1]) { inque[u.x][u.y][1] = 1; que.push(State(u.x, u.y, 1)); } } } } int main() { freopen("camelot.in", "r", stdin); freopen("camelot.out", "w", stdout); scanf("%d%d", &M, &N); char tp[5]; int tpy; scanf("%s%d", tp, &tpy); kx = tp[0]-'A'; ky = tpy - 1; for(int i=0; i<N; i++) for(int j=0; j<M; j++) kcost[i][j] = kingcost[i][j] = max(abs(i-kx), abs(j-ky)); memset(cost, 0, sizeof(cost)); while(scanf("%s%d", tp, &tpy) == 2) { int knx = tp[0]-'A', kny = tpy - 1; bfs(knx, kny); for(int i=0; i<N; i++) for(int j=0; j<M; j++) { if(dis[i][j][0] == 0x3f3f3f3f) //骑士不可能到达这一点的情况 { cost[i][j] = 0x3f3f3f3f; continue; } cost[i][j] += dis[i][j][0]; kcost[i][j] = min(kcost[i][j], dis[i][j][1]-dis[i][j][0]); } } int res = 0x3fffffff; for(int i=0; i<N; i++) for(int j=0; j<M; j++) { res = min(res, cost[i][j]+kcost[i][j]); } printf("%d ", res); return 0; }