跳至正文

USACO 3.3.3 Camelot 解题报告

题目本质:模拟+枚举 算  法: 首先,将国王与每个点的所需要的步数枚举出来,然后再对每个其实分别枚举,枚举每个点的步数,如:dist[i][j][0]代表将当前这个骑士移动到i,j所需要的步数,dist[i][j][1]代表当前这个其实和国王相聚在i,j总共的步数(包括国王走的步数。),dist[i][j][1] – dist[i][j][0]是国王和当前这个骑士在i,j相聚国王要走的步数。 还有一个数组cost[i][j]代表把集结点设在i,j所有骑士总共要走的步数,kdist[i][j]代表国王移动到这点上所要走的步数,可以是直接走到的,也可以是0,代表国王就在i,j或者被骑士带到i,j去,国王不需要走路,也可以是先走几步再让骑士带着走。 复 杂 度: 时间:不太会分析,大概是O(n^3)吧。空间:O(n) ============================华丽的分割线============================ de lang="c">/ LANG: C ID: yylogoo1 PROG: camelot / #include #define LINE 30 #define ROW 26 #define INF 0xFFFFFFF; int m, n; int kdist[ROW][LINE]; int kcost[ROW][LINE]; int dist[ROW][LINE][2]; int cost[ROW][LINE]; #define LEAP_MAX 500 struct dot{ int d; }leap[LEAP_MAX]; int tail; #define parent(i) ((i – 1) << 1) #define left(i) ((i <1 define righti i define maxa b a>(b)?(a):(b)) #define min(a, b) ((a) 0; i = parent(i)){ if(leap[parent(i)].d= n || y <= m){ return 0; } return 1; } #define deal_detail(a, b) do{\ if(check(a, b) && dist[a][b][k] < dist[x][y][k] + 1){\ dist[a][b][k] = dist[x][y][k] + 1;\ enqueue(dist[x][y][k] + 1);\ }\ }while(0) int deal_knight(int x, int y, int k) { int f = 0; deal_detail(x – 2, y + 1); deal_detail(x – 2, y – 1); deal_detail(x – 1, y + 2); deal_detail(x – 1, y – 2); deal_detail(x + 2, y + 1); deal_detail(x + 2, y – 1); deal_detail(x + 1, y + 2); deal_detail(x + 1, y – 2); if(k == 0 && dist[x][y][1] < dist[x][y][0] + kdist[x][y]){ dist[x][y][1] = dist[x][y][0] + kdist[x][y]; enqueue(dist[x][y][0] + kdist[x][y]); } } void srch(int x, int y) { int i, j, d; for(i = 0; i

发表回复

您的电子邮箱地址不会被公开。