POJ 1178

这道题做的让自己很惭愧

一开始想不出来思路，后来只好放弃看题解却发现如此简单。就是把问题拆解为三个部分，king让谁接，在哪里接，重点设置在哪，枚举即可

预处理就是floyd算出所有节点之间距离

可是预处理的时候犯了一个很严重的错误，因为把整个棋盘为了转化为一个图，就把每个格子2维坐标降维改成一字排开，计算下一步移动当时也就改成在一维增量，例如(-2, -1)就对应转化为(-2*64-1)。但是在判断下一步能否还在棋盘内的时候，必须要还原到二维。比如正好在边界，然后跳到一个本该出界的位置，但是按照这种计算下一步的方法，下一步还是在棋盘64个节点里面，本质原因就是同一个数有两种表示方法，而我这种下一步处理，没有办法保证这个数是由一个惟一坐标得出的

提交时还WA了好几次，改了下读取输入发现过来，有时候真是玄学

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int maxn= 66;
const int V= 64;
const int INF= 0x3f3f3f3f;
const int width= 8;

int ndv[maxn][maxn], kdv[maxn][maxn];
int nt_step[8][2]= {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
int kg_step[8][2]= {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int p[maxn];
string s;

void Init()
{
	for (int i= 0; i< V; ++i){
		for (int j= i+1; j< V; ++j){
			kdv[i][j]= kdv[j][i]= INF;
			ndv[i][j]= ndv[j][i]= INF;
		}
		kdv[i][i]= ndv[i][i]= 0;
	}
	for (int i= 0; i< V; ++i){
		int nx, ny, kx, ky;
		for (int j= 0; j< 8; ++j){
			ky= (i>>3)+kg_step[j][0];
			kx= (i&7)+kg_step[j][1];
			ny= (i>>3)+nt_step[j][0];
			nx= (i&7)+nt_step[j][1];
			if (nx>= 0 && nx < width && ny>= 0 && ny< width){
				ndv[i][(ny<<3)+nx]= 1;
			}
			if (kx>= 0 && kx < width && ky>= 0 && ky< width){
				kdv[i][(ky<<3)+kx]= 1;
			}
		}
	}
	// floyd
	for (int k= 0; k< V; ++k){
		for (int i= 0; i< V; ++i){
			for (int j= 0; j< V; ++j){
				ndv[i][j]= min(ndv[i][j], ndv[i][k]+ndv[k][j]);
				kdv[i][j]= min(kdv[i][j], kdv[i][k]+kdv[k][j]);
			}
		}
	}
}
int main()
{
	Init();
	cin>>s;
	int sz= s.size();
	int x, y, tot= 0;
	for (int i= 0; i< sz; i+= 2){
		x= s[i]-'A';
		y= s[i+1]-'1';
		p[tot++]= (y<<3)+x;
	}

	int ans= tot == 0 ? 0 : INF;
	for (int dst= 0; dst< V; ++dst){
		for (int wt= 0; wt< V; ++wt){
			int tmp= kdv[p[0]][wt]+ndv[wt][dst];
			for (int q= 1; q< tot; ++q){
				tmp+= ndv[p[q]][dst];
			}
			for (int k= 1; k< tot; ++k){
				ans= min(ans, tmp-ndv[p[k]][dst]+ndv[p[k]][wt]);
			}
		}
	}

	printf("%d
", ans);

	return 0;
}