| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
虽然参考了别人的思路,但是还要200题留念,1A,32ms,呈上源码#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> P;
const int oo = 0x3f3f3f3f;
int dist_king[64][64];
int dist_knight[64][64];
int dx1[] = {-1,1,0,0,-1,-1, 1,1};
int dy1[] = {0,0,-1,1,-1, 1,-1,1};
int dx2[] = {-2,-1,1,2, 2, 1,-1,-2};
int dy2[] = { 1, 2,2,1,-1,-2,-2,-1};
char input_str[63 * 2 + 1];
int kx,ky;
int N_K;
P knights[63];
void Graph_Init(){
memset(dist_king, oo, sizeof(dist_king));
memset(dist_knight, oo, sizeof(dist_knight));
for (int i = 0; i < 64; ++i) {
dist_knight[i][i] = dist_king[i][i] = 0;
}
for (int i = 0; i < 64; ++i) {
int x = i % 8;
int y = i / 8;
for (int j = 0; j < 8; ++j) {
int nx = x + dx1[j];
int ny = y + dy1[j];
if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8){
dist_king[i][ny * 8 + nx] = dist_king[ny * 8 + nx][i] = 1;
}
}
}
for (int i = 0; i < 64; ++i) {
int x = i % 8;
int y = i / 8;
for (int j = 0; j < 8; ++j) {
int nx = x + dx2[j];
int ny = y + dy2[j];
if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8){
dist_knight[i][ny * 8 + nx] = dist_knight[ny * 8 + nx][i] = 1;
}
}
}
}
void Folyd(){
for (int k = 0; k < 64; ++k) {
for (int i = 0; i < 64; ++i) {
for (int j = 0; j < 64; ++j) {
dist_king[i][j] = min(dist_king[i][j], dist_king[i][k] + dist_king[k][j]);
}
}
}
for (int k = 0; k < 64; ++k) {
for (int i = 0; i < 64; ++i) {
for (int j = 0; j < 64; ++j) {
dist_knight[i][j] = min(dist_knight[i][j], dist_knight[i][k] + dist_knight[k][j]);
}
}
}
}
int main(){
scanf("%s", input_str);
kx = input_str[0] - 'A';
ky = input_str[1] - '1';
N_K = strlen(input_str) / 2 - 1;
for (int i = 0; i < N_K; ++i) {
knights[i].first = input_str[2 + (i * 2)] - 'A';
knights[i].second = input_str[2 + (i * 2) + 1] - '1';
}
Graph_Init();
Folyd();
int res = oo;
for (int end_loc = 0; end_loc < 64; ++end_loc) {
for (int meet_loc = 0; meet_loc < 64; ++meet_loc) {
for (int meet_knight = 0; meet_knight < N_K; ++meet_knight) {
int sum_dist = 0;
for (int i = 0; i < N_K; ++i) {
if (i == meet_knight){
continue;
}
sum_dist += dist_knight[knights[i].first + 8 * knights[i].second][end_loc];
}
sum_dist += dist_king[kx + 8 * ky][meet_loc];
sum_dist += dist_knight[knights[meet_knight].first + 8 * knights[meet_knight].second][meet_loc];
sum_dist += dist_knight[meet_loc][end_loc];
res = min(res, sum_dist);
}
}
}
printf("%d\n", res);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator