USACO 3.3 Camelot

Camelot
IOI 98

Centuries ago, King Arthur and the Knights of the Round Table used to meet every year on New Year's Day to celebrate their fellowship. In remembrance of these events, we consider a board game for one player, on which one chesspiece king and several knight pieces are placed on squares, no two knights on the same square.

This example board is the standard 8x8 array of squares:

The King can move to any adjacent square from to as long as it does not fall off the board:

A Knight can jump from to , as long as it does not fall off the board:

During the play, the player can place more than one piece in the same square. The board squares are assumed big enough so that a piece is never an obstacle for any other piece to move freely.

The player's goal is to move the pieces so as to gather them all in the same square - in the minimal number of moves. To achieve this, he must move the pieces as prescribed above. Additionally, whenever the king and one or more knights are placed in the same square, the player may choose to move the king and one of the knights together from that point on, as a single knight, up to the final gathering point. Moving the knight together with the king counts as a single move.

Write a program to compute the minimum number of moves the player must perform to produce the gathering. The pieces can gather on any square, of course.

PROGRAM NAME: camelot

INPUT FORMAT

Line 1:	Two space-separated integers: R,C, the number of rows and columns on the board. There will be no more than 26 columns and no more than 30 rows.
Line 2..end:	The input file contains a sequence of space-separated letter/digit pairs, 1 or more per line. The first pair represents the board position of the king; subsequent pairs represent positions of knights. There might be 0 knights or the knights might fill the board. Rows are numbered starting at 1; columns are specified as upper case characters starting with `A'.

SAMPLE INPUT (file camelot.in)

8 8
D 4
A 3 A 8
H 1 H 8

The king is positioned at D4. There are four knights, positioned at A3, A8, H1, and H8.

OUTPUT FORMAT

A single line with the number of moves to aggregate the pieces.

SAMPLE OUTPUT (file camelot.out)

SAMPLE OUTPUT ELABORATION

They gather at B5.
Knight 1: A3 - B5 (1 move)
Knight 2: A8 - C7 - B5 (2 moves)
Knight 3: H1 - G3 - F5 - D4 (picking up king) - B5 (4 moves)
Knight 4: H8 - F7 - D6 - B5 (3 moves)
1 + 2 + 4 + 3 = 10 moves.

————————————————————————

看着这道题第一眼觉得我见过，好像是枚举，然后n³挂得毫无疑问

嗯其实是最短路问题，网上说的枚举都是简化题面了，和华容道有点类似【华容道多加了一维方向做状态】，就是要多加一维带王或者不带王的状态做spfa

第一步处理王到棋盘的所有最短路

第二步处理某个骑士到棋盘各处的最短路的同时，加一维状态0/1记录骑士是否带王，使用堆优，每次更新0的时候顺带就更新1【也就是设某个点p，我们初始把所有最短路刷成inf后，第一次更新1就相当于王到p的最短路和骑士到p的最短路之和，也就是shortest_path_of_knight[p][0]+shortest_path_of_king[p]】

超级快，最慢不到0.3s

两行老泪……终于AC了……

  1 /*
  2 ID: ivorysi
  3 PROG: camelot
  4 LANG: C++
  5 */
  6 #include <iostream>
  7 #include <cstdio>
  8 #include <cstring>
  9 #include <algorithm>
 10 #include <queue>
 11 #include <set>
 12 #include <vector>
 13 #include <string.h>
 14 #define siji(i,x,y) for(int i=(x);i<=(y);++i)
 15 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
 16 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
 17 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
 18 #define inf 0x3f3f3f3f
 19 #define MAXN 400005
 20 #define ivorysi
 21 #define mo 97797977
 22 #define ha 974711
 23 #define ba 47
 24 #define fi first
 25 #define se second
 26 #define pii pair<int,int>
 27 using namespace std;
 28 typedef long long ll;
 29 int sp[805][2];
 30 int knivis[805][2];
 31 int vis[35][35];
 32 int ksp[805];
 33 int kingcost[805];
 34 int r,c;
 35 int ky[8]={1,2,2,1,-1,-2,-2,-1};
 36 int kx[8]={2,1,-1,-2,-2,-1,1,2};
 37 int kj[8]={1,1,1,0,-1,-1,-1,0};
 38 int ki[8]={1,0,-1,-1,-1,0,1,1};
 39 struct node {
 40     int rr,cc,step;
 41 };
 42 queue<node> q;
 43 void pre1(int u) {
 44     memset(vis,0,sizeof(vis));
 45     int cx=(u-1)%c+1,rx=(u-1)/c+1;
 46     while(!q.empty()) q.pop();
 47     q.push((node){rx,cx,0});
 48     vis[rx][cx]=1;
 49     while(!q.empty()) {
 50         node nw=q.front();q.pop();
 51         kingcost[(nw.rr-1)*c+nw.cc]=ksp[(nw.rr-1)*c+nw.cc]=nw.step;
 52         siji(i,0,7) {
 53             int z=nw.rr+ki[i],w=nw.cc+kj[i];
 54             if(z<=r&&z>=1&&w<=c&&w>=1&& vis[z][w]==0) {
 55                 vis[z][w]=1;
 56                 q.push((node){z,w,nw.step+1});
 57             }
 58         }
 59     }
 60 }
 61 struct data{
 62     int rr,cc,cking,step;
 63     bool operator < (const data &rhs) const{
 64         return step>rhs.step;
 65     }
 66 };
 67 priority_queue<data> q1;
 68 void spfa(int u) {
 69     memset(sp,inf,sizeof(sp));
 70     memset(knivis,0,sizeof(vis));
 71     while(!q1.empty()) q1.pop();
 72     int cx=(u-1)%c+1,rx=(u-1)/c+1;
 73     q1.push((data){rx,cx,0,0});
 74     sp[u][0]=0;
 75     knivis[u][0]=1;
 76     while(!q1.empty()) {
 77         data nw=q1.top();q1.pop();
 78         siji(i,0,7) {
 79             int z=nw.rr+kx[i],w=nw.cc+ky[i];
 80             if(z<=r&&z>=1&&w<=c&&w>=1) {
 81                 if(sp[(z-1)*c+w][nw.cking]>nw.step+1) {
 82                     sp[(z-1)*c+w][nw.cking]=nw.step+1;
 83                     if(!knivis[(z-1)*c+w][nw.cking]){
 84                         knivis[(z-1)*c+w][nw.cking]=1;
 85                         q1.push((data){z,w,nw.cking,nw.step+1});
 86                     }
 87                 }
 88             }
 89         }
 90         if(nw.cking==0 && sp[(nw.rr-1)*c+nw.cc][1]>nw.step+ksp[(nw.rr-1)*c+nw.cc]) {
 91             sp[(nw.rr-1)*c+nw.cc][1]=nw.step+ksp[(nw.rr-1)*c+nw.cc];
 92             if(!knivis[(nw.rr-1)*c+nw.cc][1]){
 93                 knivis[(nw.rr-1)*c+nw.cc][1]=1;
 94                 q1.push((data){nw.rr,nw.cc,1,sp[(nw.rr-1)*c+nw.cc][1]});
 95             }
 96         }
 97         knivis[(nw.rr-1)*c+nw.cc][nw.cking]=0;
 98     }
 99 
100 }
101 int king,kni[805],cnt;
102 int dist[805];
103 void init(){
104     scanf("%d%d",&r,&c);
105     char str[5];int b;
106     char s;
107     scanf("%s%d",str,&b);
108     siji(i,0,4) if(str[i] >='A'&&str[i]<='Z') {s=str[i];break;}
109     king=(b-1)*c+s-'A'+1;
110     while(1){
111         scanf("%s %d",str,&b);
112         if(b==0) break;
113         siji(j,0,4) if(str[j] >='A'&&str[j]<='Z') {s=str[j];break;}
114         kni[++cnt]=(b-1)*c+s-'A'+1;
115         b=0;
116     }
117     pre1(king);
118     
119 }
120 void solve() {
121     init();
122     siji(i,1,cnt) {
123         spfa(kni[i]);
124         siji(j,1,r*c) {
125             if(sp[j][0]==inf||dist[j]==-1) {dist[j]=-1;continue;}
126             dist[j]+=sp[j][0];
127             kingcost[j]=min(kingcost[j],sp[j][1]-sp[j][0]);
128         }
129     }
130     int ans=inf;
131     siji(j,1,r*c) {
132         if(dist[j]==-1) continue;
133         ans=min(kingcost[j]+dist[j],ans);
134     }
135     printf("%d
",ans);
136 }
137 int main(int argc, char const *argv[])
138 {
139 #ifdef ivorysi
140     freopen("camelot.in","r",stdin);
141     freopen("camelot.out","w",stdout);
142 #else
143     freopen("f1.in","r",stdin);
144 #endif
145     solve();
146 }