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