链接：
http://acm.hdu.edu.cn/showproblem.php?pid=3955这题的《Civilization》背景导致不少没玩过这款经典游戏的acmer悲剧了。这。。。表示还好没被读题坑了。。。不过敲着敲着就发现一处关键点没处理的时候感觉实在是太蛋疼了。。。果然这种比较恶心的题，要先设计好状态再开搞才是正确策略。
100*100的有限制地图，给一个起点，给一个终点，给一个行动值，问最小回合数是多少。
行动值和回合数：当行动值为0时结束回合，到下一回合。特例是，如果所剩行动值不为0但是小于任何移动所需的行动值，则可以强行行动，然后行动值归零。
地图限制：
用读入的数字来解析地图上的每一点，分为有/无森林，有/无敌人，是/否敌人占领区，六向有/无河等几种状态。
搜索的时候，注意条件的优先级：
首先判断是否敌人，如果是，则该点不可访问；
其次判断是否为敌占区（敌人周围6格），如果当前点和到达点都是敌占区（另外一个标记数组来记），那么只要移动，行动值就清零。
再判断是否道路，如果当前点和到达点都有道路（另外一个标记数组来记），那么移动花费只有0.25.
再判断有无河流，如果前往方向有何流，则行动值清零。
最后判断地形，根据有无森林判断是耗费1还是2行动值。
这个题目的要点就这些。说一下自己被坑的地方。
由于，道路和敌占区都要相连才能起作用，所以单独的这两者都是没用的，需要按照其原来状态标记，所以这两种情况需要另开标记数组来标记。
还有地图的优先级，记得低优先级的情况不要把高优先级的情况覆盖掉（比如不要用森林什么的覆盖掉敌人或者敌占区。。）
最后是搜索的时候，不要犯2.。。我今天写了个”加枝搜索“，自2了。。。
初始值是全部inf，出发点为1（为1啊少年！）。
搜索更新状态的时候，turn（回合数）因为和往常的普通bfs不同，可以不用+1（只要在出队的时候判断是否需要加1即可）；
但是不能把MP值做相同的处理，如果【当前状态+转移】比【目标状态】更优的话，一定要用【当前状态+转移】更新【目标状态】。。而非【当前状态】自身。。
这个就是TLE和AC的关键差别啊～～！我了个去～！～！！！！
这道题用Priority First Search(PFS)比BFS要快一点。
我一开始还以为是状态转移过程中参量太多导致了TLE，所以把int和double都改成了short和float。好吧，我是个2B.今天我蒟蒻了。
啊啊啊啊啊啊啊。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define maxn 105
using namespace std;
const short inf = 20000;
bool con[maxn][maxn][7];
int mat[maxn][maxn];
bool road[maxn][maxn];
bool zoc[maxn][maxn];
int n,m,MP;
int stx,sty,enx,eny;
const double eps = 1e-6;
int comp(double x)
{
if(fabs(x) < eps)
return 0;
else if(x < -eps)
return -1;
else
return 1;
}
struct status
{
short x,y,turn;
float mp;
status(){}
status(short _x,short _y,float _m,short _t):x(_x),y(_y),mp(_m),turn(_t){}
};
bool operator < (const status a,const status b)
{
return (a.turn > b.turn || (a.turn == b.turn && comp(a.mp - b.mp) < 0));
}
struct dist
{
short turn;
float mp;
dist(){}
dist(float _m,int _t):turn(_t),mp(_m){}
} dis[maxn][maxn];
/*
6 nw
5 w
4 sw
3 se
2 e
1 ne
*/
char dx1[] = {0,-1,0,1,1,0,-1};//even
char dy1[] = {0,1,1,1,0,-1,0};
char dx2[] = {0,-1,0,1,1,0,-1};//odd
char dy2[] = {0,0,1,0,-1,-1,-1};
bool check(int x,int y)
{
return (1 <= x && x <= n && 1 <= y && y <= m);
}
void bfs()
{
priority_queue <status> Q;
Q.push(status(stx,sty,MP,1));
dis[stx][sty] = dist(MP,1);
while(!Q.empty())
{
status now = Q.top();
Q.pop();
if(now.x == enx && now.y == eny)
break;
if(comp(now.mp) <= 0)
{
now.mp = MP;
now.turn ++;
}
for(int i = 1;i <= 6;i++)
{
int x,y;
if(now.x % 2 == 0)
{
x = now.x + dx1[i];
y = now.y + dy1[i];
}
else
{
x = now.x + dx2[i];
y = now.y + dy2[i];
}
float pm = now.mp;
if(!check(x,y) || mat[x][y] == 3)
continue;
else if(zoc[x][y] == 1 && zoc[now.x][now.y] == 1)
{
if(dis[x][y].turn > now.turn || (dis[x][y].turn == now.turn && comp(dis[x][y].mp) < 0))
{
Q.push(status(x,y,0,now.turn));
dis[x][y] = dist(0,now.turn);
}
}
else if(road[x][y] == true && road[now.x][now.y] == true)
{
if(dis[x][y].turn > now.turn || (dis[x][y].turn == now.turn && comp(dis[x][y].mp - (pm - 0.25)) < 0))
{
Q.push(status(x,y,pm - 0.25,now.turn));
dis[x][y] = dist(pm - 0.25,now.turn);
}
}
else if(con[now.x][now.y][i] == 1)
{
if(dis[x][y].turn > now.turn || (dis[x][y].turn == now.turn && comp(dis[x][y].mp) < 0))
{
Q.push(status(x,y,0,now.turn));
dis[x][y] = dist(0,now.turn);
}
}
else if(mat[x][y] == 1)
{
if(dis[x][y].turn > now.turn || (dis[x][y].turn == now.turn && comp(dis[x][y].mp - (pm - 2)) < 0))
{
Q.push(status(x,y,pm - 2,now.turn));
dis[x][y] = dist(pm - 2,now.turn);
}
}
else if(mat[x][y] == 0)
{
if(dis[x][y].turn > now.turn || (dis[x][y].turn == now.turn && comp(dis[x][y].mp - (pm - 1)) < 0))
{
Q.push(status(x,y,pm - 1,now.turn));
dis[x][y] = dist(pm - 1,now.turn);
}
}
}
}
}
/*
0 cost 1
1 cost 2
3 can't
*/
void fuck(int x,int y)
{
for(int i = 1;i <= 6;i++)
{
if(x % 2 == 0 && check(x + dx1[i],y + dy1[i]))
zoc[x + dx1[i]][y + dy1[i]] = true;
else
{
if( check(x + dx2[i],y + dy2[i]))
zoc[x + dx2[i]][y + dy2[i]] = true;
}
}
}
void gao()
{
scanf("%d %d %d",&n,&m,&MP);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
road[i][j] = 0;
mat[i][j] = -1;
zoc[i][j] = 0;
}
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
{
int opt;
scanf("%d",&opt);
for(int k = 9;k >= 0;k--)
{
if(opt >= (1 << k))
{
opt -= (1 << k);
if(k > 3)
con[i][j][k - 3] = true;
else
{
if(k == 3)
{
mat[i][j] = 3;
fuck(i,j);
}
else
{
if(mat[i][j] == -1)
mat[i][j] = k;
if(mat[i][j] == 2)
{
mat[i][j] = k;
road[i][j] = true;
}
}
}
}
else
{
if(k > 3)
con[i][j][k - 3] = false;
}
}
}
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
dis[i][j] = dist(0,inf);
scanf("%d %d %d %d",&stx,&sty,&enx,&eny);
stx++;
sty++;
enx++;
eny++;
bfs();
int ans = dis[enx][eny].turn;
printf("%d\n",(ans == inf?-1:ans));
}
int main()
{
int t;
scanf("%d",&t);
for(int i = 1;i <= t;i++)
{
printf("Case %d: ",i);
gao();
}
}
å
forward sentence