題意：
? ? ? 有一個國王和很多騎士，他們都要到某一個點去集合，然后問所有人都到達某個終點的距離和最小是多少？過程中如果國王遇到了一個騎士的話，國王就可以和騎士一起按照騎士的走法走，這是兩個人算一個人，同時國王有八種走法，騎士也有八種走法，兩個不一樣。


思路：

? ? ? 可以枚舉終點，和騎士相交的點還有和那個騎士相交，只要確定這三個點后距離就出來了，求距離可以用廣搜預處理，也可以用最短路預處理，不管用什么記得細心點，還有對于國王的最短路直接可以算出來，就是max(abs(x1-x2),abs(y1-y2))。

#include<queue> #include<stdio.h> #include<string.h>#define N 70 #define INF 1000000000using namespace std;typedef struct {int x ,y ,t; }NODE;NODE xin ,tou; NODE node[N]; int dis[N][N]; int mark[N]; int dir[8][2] = {1 ,2 ,1 ,-2 ,-1 ,2 ,-1 ,-2 ,2 ,1 ,2 ,-1 ,-2 ,1 ,-2 ,-1};int minn(int x ,int y) {return x < y ? x : y; }int maxx(int x ,int y) {return x > y ? x : y; }int abss(int x) {return x > 0 ? x : -x; }bool ok(int x ,int y) {return x >= 1 && x <= 8 && y >= 1 && y <= 8 && !mark[(x-1)*8+y]; }void BFS(int x ,int y) {queue<NODE>q;xin.x = x ,xin.y = y ,xin.t = 0;memset(mark ,0 ,sizeof(mark));mark[(x-1)*8+y] = 1;dis[(x-1)*8+y][(x-1)*8+y] = 0;q.push(xin);while(!q.empty()){tou = q.front();dis[(x-1)*8+y][(tou.x-1)*8+tou.y] = tou.t;q.pop();for(int i = 0 ;i < 8 ;i ++){xin.x = tou.x + dir[i][0];xin.y = tou.y + dir[i][1];xin.t = tou.t + 1;if(ok(xin.x ,xin.y)){mark[(xin.x-1)*8+xin.y] = 1;q.push(xin);}}}return ; }int main () {char str[150];int i ,j ,k ,x ,y;for(i = 1 ;i <= 8 ;i ++)for(j = 1 ;j <= 8 ;j ++)BFS(i ,j);while(~scanf("%s" ,str)){int len = strlen(str);int id = 0;for(i = 0 ;i < len ;i += 2){x = str[i+1] - '0';y = str[i] - 'A' + 1;node[++id].x = x;node[id].y = y;}int ans = INF;for(i = 1 ;i <= 64 ;i ++) //終點for(j = 1 ;j <= 64 ;j ++) //相遇點for(k = 2 ;k <= id ;k ++) //相遇的那個騎士{int s = 0;x = (j-1) / 8 + 1;y = j % 8;if(!y) y = 8;s = maxx(abss(x - node[1].x),abss(y - node[1].y));s += dis[(node[k].x - 1) * 8 + node[k].y][j];s += dis[j][i];for(int w = 2 ;w <= id ;w ++){if(w == k) continue;s += dis[(node[w].x-1)*8+node[w].y][i];}if(s < ans) ans = s;}if(id == 1) ans = 0;printf("%d\n" ,ans);}return 0;}

總結

以上是生活随笔為你收集整理的POJ1178枚举三个地方（所有点都去同一个点）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。