Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

虽然参考了别人的思路,但是还要200题留念,1A,32ms,呈上源码

Posted by vjubge4 at 2019-04-08 14:41:53 on Problem 1178
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator