POJ 1178 - Camelot （枚举+dp : floyd）

本文主要是介绍POJ 1178 - Camelot （枚举+dp : floyd），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击打开链接

参考了别人的代码，加上了一些注释。

懂得了将一个类似与棋盘的东西转化成用邻接矩阵表示的图，然后再通过最短路相关算法求最短路。

/************************************************************************
poj 1178 (IOI 1998) - dp : floyd
枚举64个终点 * 枚举64个接国王点 * 枚举64只来接的骑士
总复杂度O(64*64*64)                                                                     
************************************************************************/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define MAX 8
const int INF = ( 1 << 20 );
int dirKing[8][2] = {{1, 0}, { -1, 0}, {0, 1}, {0, -1}, {1, 1}, { -1, -1}, {1, -1}, { -1, 1}};
int dirKnight[8][2] = {{ -2, -1}, { -2, 1}, {2, -1}, {2, 1}, { -1, -2}, {1, -2}, { -1, 2}, {1, 2}};char str[MAX*MAX * 2 + 5];
int king[MAX*MAX][MAX*MAX], knight[MAX*MAX][MAX*MAX];
int step[MAX*MAX], num;inline int min ( int a, int b )
{return a < b ? a : b;
}//建立邻接矩阵
void init()
{for ( int i = 0; i < MAX * MAX; ++i )for ( int j = 0; j < MAX * MAX; ++j )king[i][j] = knight[i][j] = ( i == j ? 0 : INF );for ( int i = 0; i < MAX * MAX; ++i ){int x = i / 8;int y = i % 8;for ( int j = 0; j < 8; ++j ){int xx = x + dirKing[j][0];int yy = y + dirKing[j][1];if ( xx >= 0 && xx < MAX && yy >= 0 && yy < MAX )king[i][8 * xx + yy] = 1;}for ( int j = 0; j < 8; ++j ){int xx = x + dirKnight[j][0];int yy = y + dirKnight[j][1];if ( xx >= 0 && xx < MAX && yy >= 0 && yy < MAX )knight[i][8 * xx + yy] = 1;}}
}void floyd ( int a[][MAX*MAX] )
{for ( int k = 0; k < MAX * MAX; ++k ){for ( int i = 0; i < MAX * MAX; ++i ){for ( int j = 0; j < MAX * MAX; ++j ){if ( a[i][j] > a[i][k] + a[k][j] )a[i][j] = a[i][k] + a[k][j];}}}
}int main()
{freopen("in.txt","r",stdin);init();floyd ( king );floyd ( knight );while ( scanf ( "%s", str ) != EOF ){int start = ( str[0] - 'A' ) + ( str[1] - '1' ) * 8;int num = ( strlen ( str ) - 2 ) / 2;if ( num == 0 ){printf ( "0\n" );continue;}for ( int i = 0, j = 2; i < num; ++i, j += 2 )step[i] = ( str[j] - 'A' ) + ( str[j + 1] - '1' ) * 8;int result = INF;int t1, t2;int sum;//枚举64个终点for ( int i = 0; i < MAX * MAX; ++i ){//sum：所有骑士到达终点的总和sum = 0;for ( int k = 0; k < num; ++k )sum += knight[ step[k] ][i];//枚举64个接国王的点for ( int j = 0; j < MAX * MAX; ++j ){t1 = king[start][j];t2 = INF;//找离国王最近的点for ( int kk = 0; kk < num; ++kk ){t2 = min ( t2, knight[ step[kk] ][j] + knight[j][i] - knight[ step[kk] ][i] ); // 骑士从起始点到达j点接国王, 骑士和国王一起到达枚举的终点, 其中要减去sum已经加上的即可.}result = min ( result, sum + t1 + t2 );}}printf ( "%d\n", result );}return 0;
}

这篇关于POJ 1178 - Camelot （枚举+dp : floyd）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---