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

## 【数字】我的解答，没做出来的看看。

Posted by 50573750 at 2011-03-08 13:01:26 on Problem 1178
```主要还是枚举！

#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

int mat_dist_kn[65][65];
int mat_dist_ki[65][65];

int dir_kn_x[8] = {-2,-2,-1,-1,1,1,2,2};
int dir_kn_y[8] = {-1,1,-2,2,-2,2,-1,1};
int dir_ki_x[8] = {-1,-1,-1,0,0,1,1,1};
int dir_ki_y[8] = {-1,0,1,-1,1,-1,0,1};

int num_kn;
int ar[65];
int pos_ki;

const static int c_max = 1000000;

int get_id(int r,int c)
{
return r*8 + c;
}

void get_r_c(int id,int &r,int &c)
{
r = id/8;
c = id%8;
}

bool check_in_board(int r,int c)
{
return (r >= 0) && (r < 8) && (c >=0 ) && (c < 8);
}

void gh_floyd(int map[][65])
{
for(int cnt = 0;cnt<64;cnt++)
{
for(int cnt_r = 0;cnt_r<64;cnt_r++)
{
for(int cnt_c=0;cnt_c<64;cnt_c++)
{
if (map[cnt_r][cnt] + map[cnt][cnt_c] < map[cnt_r][cnt_c])
map[cnt_r][cnt_c] = map[cnt_r][cnt] + map[cnt][cnt_c];
}
}
}
}

void init_map(int gh[][65],int dir_x[],int dir_y[])
{
for(int cn_src=0;cn_src<64;cn_src++)
{
for(int cn_des=0;cn_des<64;cn_des++)
{
gh[cn_src][cn_des] = c_max;
}
}

for(int cnt_pos=0;cnt_pos<64;cnt_pos++)
{
gh[cnt_pos][cnt_pos] = 0;

int r,c;
get_r_c(cnt_pos,r,c);
for(int cnt_dir=0;cnt_dir<8;cnt_dir++)
{
int next_r = r + dir_x[cnt_dir];
int next_c = c + dir_y[cnt_dir];

if (!check_in_board(next_r,next_c))
{
continue;
}

int next_id = get_id(next_r,next_c);
gh[next_id][cnt_pos] = gh[cnt_pos][next_id] = 1;
}
}
}

void init_all()
{
init_map(mat_dist_kn,dir_kn_x,dir_kn_y);
gh_floyd(mat_dist_kn);
init_map(mat_dist_ki,dir_ki_x,dir_ki_y);
gh_floyd(mat_dist_ki);
}

int main(int argc, char* argv[])
{
ifstream fin("D:\\acm\\try_1178.txt");

char a,b;
fin>>a>>b;
pos_ki = get_id(a -'A',b - '1');

while(fin)
{
fin>>a>>b;
ar[num_kn++] = get_id(a - 'A',b - '1');
}

num_kn --;

if (num_kn == 0)
cout<<"0"<<endl;

init_all();
int ans= c_max;
for(int cnt_des=0;cnt_des<64;cnt_des++)
{
int sum = 0;
for(int cnt=0;cnt<num_kn;cnt++)
{
sum += mat_dist_kn[cnt_des][ar[cnt]];
}

for(int cnt_kn=0;cnt_kn<num_kn;cnt_kn++)
{
for(int cnt_join=0;cnt_join<64;cnt_join++)
{
int cur_res = sum + mat_dist_ki[cnt_join][pos_ki] - mat_dist_kn[cnt_des][ar[cnt_kn]] + mat_dist_kn[cnt_des][cnt_join] + mat_dist_kn[cnt_join][ar[cnt_kn]];
if (cur_res < ans)
ans = cur_res;
}
}
}

cout<<ans<<endl;

return 0;
}```

Followed by: