| ||||||||||
| 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 | |||||||||
H2O题一个!先bfs祘出棋盘上任意两点的馬距离,然后暴力即可#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
using namespace std;
int dist[64][64];
bool inRange(int x, int y){
return x >= 0 && x < 8 && y >= 0 && y < 8;
}
inline int Abs(int x){
if(x >= 0) return x;
return -x;
}
void preprocess(){
for(int i = 0; i < 64; i++){
bool used[64] = {0};
used[i] = 1;
queue<int> bfs;
bfs.push(i);
dist[i][i] = 0;
while(!bfs.empty()){
int top = bfs.front();
bfs.pop();
int x = top/8, y = top%8;
if(inRange(x-1, y-2) && !used[top-10]){
used[top-10] = 1;
dist[i][top-10] = dist[i][top]+1;
bfs.push(top-10);
}
if(inRange(x-1, y+2) && !used[top-6]){
used[top-6] = 1;
dist[i][top-6] = dist[i][top]+1;
bfs.push(top-6);
}
if(inRange(x+1, y-2) && !used[top+6]){
used[top+6] = 1;
dist[i][top+6] = dist[i][top]+1;
bfs.push(top+6);
}
if(inRange(x+1, y+2) && !used[top+10]){
used[top+10] = 1;
dist[i][top+10] = dist[i][top]+1;
bfs.push(top+10);
}
if(inRange(x-2, y-1) && !used[top-17]){
used[top-17] = 1;
dist[i][top-17] = dist[i][top]+1;
bfs.push(top-17);
}
if(inRange(x-2, y+1) && !used[top-15]){
used[top-15] = 1;
dist[i][top-15] = dist[i][top]+1;
bfs.push(top-15);
}
if(inRange(x+2, y-1) && !used[top+15]){
used[top+15] = 1;
dist[i][top+15] = dist[i][top]+1;
bfs.push(top+15);
}
if(inRange(x+2, y+1) && !used[top+17]){
used[top+17] = 1;
dist[i][top+17] = dist[i][top]+1;
bfs.push(top+17);
}
}
}
}
int main() {
preprocess();
char str[250];
scanf("%s", str);
int len = strlen(str);
int gs = len/2-1;
int posKgx, posKgy;
int posKnx[64], posKny[64];
posKgx = (str[0]-'A'), posKgy = (str[1]-'1');
for(int i = 0; i < gs; i++){
posKnx[i] = (str[2*i+2]-'A'), posKny[i] = (str[2*i+3]-'1');
}
int mn = 2147483647;
for(int rdz = 0; rdz < 64; rdz++){
int rdzx = rdz/8, rdzy = rdz%8;
int mnK = Abs(rdzx-posKgx) + Abs(rdzy-posKgy);
for(int i = 0; i < gs; i++){
mnK += dist[rdz][posKnx[i]*8+posKny[i]];
}
for(int getOn = 0; getOn < 64; getOn++){
if(getOn == rdz) continue;
int getOnx = getOn/8, getOny = getOn%8;
int temp = Abs(getOnx-posKgx) + Abs(getOny-posKgy);
int dz = 2147483647;
for(int i = 0; i < gs; i++){
int iP = posKnx[i]*8+posKny[i];
int duozou = dist[iP][getOn] + dist[getOn][rdz] - dist[iP][rdz];
if(duozou < dz){
dz = duozou;
}
}
temp += dz;
for(int i = 0; i < gs; i++){
temp += dist[posKnx[i]*8+posKny[i]][rdz];
}
if(temp < mnK) mnK = temp;
}
if(mnK < mn) mn = mnK;
}
printf("%d\n", mn);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator