有一段日子木有更新solution神马的，北京区域赛的准备工作好烦哪。强烈要求出现一个组委会，而不是我们这帮集训队的来干各种奇葩活。
言归正传，9月的浙大月赛可搞题颇多，场上就想写这题，可惜木有机时，只能场下写咯。可惜一写就掉坑里了，直到现在才爬出来，好恶心的一道题啊。
题意：
10*10的棋盘，有一个你控制的棋子A，每步可四向移动；有一个镜像棋子B，和你呈镜像运动，遇边、石则当前回合不动；路上有石头，不可入；有压路机，循环运动，遇神杀神，遇石回头；地图上有<=5个宝石，你需要用A去拾取全部（WA点1，用A拾取，B没用）；有两个出口，需要让A、B同时到达这俩出口，且拿满宝石，则你赢了。被压路机压到A、B或者同时到达出口时宝石没拿满，都是死。
做法：
就是BFS+模拟，模拟的规则略复杂。
先说状态，压路机方向 + 压路机位置 + A位置 + B位置 + 五块宝石的拿取状态。最后一个状态我用2^5来存，所以整体是一个9位数（虽说大牛们说前两个状态因为压路机的循环移动性质乘起来只有20种）。整体状态数=2 * 10 * 100 * 100 * 32 = 6400000 ，果断hash。一开始用MAP，TLE了；后来只能手写hash了，不仅要记hash之前的状态值还需要记对应状态的权值，难怪那么大内存。
接着就是模拟了：
每次解hash（注意hash数字时候的顺序）得取当前状态，然后算出下一回合A、B、压路机K的位置和宝石状态。
但是判定非法的时候，需要按顺序判断：
因为走的顺序是A、B、K，所以先判断A，check（超范围、碰R），碰K（未动），碰B，碰到则状态非法；再判断B，若碰新A，check，碰K，则不动。先不判K。
然后判断A是否拿到了新的宝石。
此时要判断A、B是否达到了出口，如果达到了而宝石不齐，则状态非法（wa点2）；若齐了，则更新最短路长（不要在出队以后再更新，要在入队前更新，否则压路机会把这种情况给判非法掉）。只要达到出口，则状态不进队。
最后判K，吃了A或者B则状态非法。（WA点3）
代码写的好矬啊，别人800ms过，我wa+tle了两版才2400ms过。。。蒟蒻伤不起啊。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
#define maxn 11
#define hashsize (6400013)
#define maxm (hashsize + 10)
int ans;
const int inf = 1 << 30;
char mst[maxn][maxn];
int vis[maxm];
int cas;
int tot;
struct HASH
{
int x,step;
HASH(){}
HASH(int _x,int _s):x(_x),step(_s){}
}h[maxm];
inline int find(int x)
{
int z = x % hashsize;
return vis[z] == cas?h[z].step:-1;
}
inline void insert(int x,int value)
{
int z = x % hashsize;
vis[z] = cas;
h[z] = HASH(x,value);
}
inline void update(int x,int value)
{
int z = x % hashsize;
h[z].step = value;
}
struct node
{
int x,y;
node(){}
node(int a,int b):x(a),y(b){}
bool operator ==(const node p)
{
return x == p.x && y == p.y;
}
}pa,pb,en[2],ki,pc[6];
int r,c;
int pcs;
char dir;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
char rd[] = {'N','S','W','E'};
int co(char _d)
{
for(int i = 0;i < 4;i++)
if(rd[i] == _d)
return i;
}
int hash(int _d,node p[],bool gd[])
{
int x = 0;
for(int i = 0;i < pcs;i++)
if(gd[i])
x |= (1 << i);
int idx = 100;
for(int i = 2;i >= 0;i--)
{
x += idx * p[i].x;
idx *= 10;
x += idx * p[i].y;
idx *= 10;
}
x += (_d + 1) * idx;
return x;
}
inline bool check(int x,int y)
{
return 0 <= x && x < r && 0 <= y && y < c && mst[x][y] != 'R';
}
void bfs()
{
queue <int> Q;
bool gd[6];
for(int i = 0;i < pcs;i++)
gd[i] = true;
node p[3];
p[0] = ki;
p[1] = pa;
p[2] = pb;
int s = hash(co(dir),p,gd);
//cout << s << endl;
if(find(s) == -1)
insert(s,0);
Q.push(s);
//cout << s << endl;
while(!Q.empty())
{
int now = Q.front();
Q.pop();
//cout << now << endl;
int step = find(now);
int idx = 100000000;
int tdir = now / idx - 1;
now -= (tdir+1) * idx;
idx /= 10;
//cout << now << endl;
for(int i = 0;i < 3;i++)
{
p[i].y = now / idx;
now -= p[i].y * idx;
idx /= 10;
p[i].x = now / idx;
now -= p[i].x * idx;
idx /= 10;
}
//cout << now << endl;
int x,y;
x = p[0].x + dx[tdir];
y = p[0].y + dy[tdir];
if(!check(x,y))
{
x = p[0].x;
y = p[0].y;
tdir ^= 1;
}
node tk = node(x,y);
for(int i = 0;i < 4;i++)
{
bool dg[6] = {0};
int ax = p[1].x + dx[i],ay = p[1].y + dy[i];
int bx = p[2].x + dx[i^1],by = p[2].y + dy[i^1];
if(!check(ax,ay) || node(ax,ay) == p[0] || node(ax,ay) == p[2])//they can stay in the same point???
continue;
if(!check(bx,by) || node(bx,by) == p[0] || node(bx,by) == node(ax,ay))
{
bx = p[2].x;
by = p[2].y;
}
int what = 0;
for(int j = 0;j < pcs;j++)
if(((now >> j) & 1) && !(node(ax,ay) == pc[j]))
{
dg[j] = 1;
what |= 1 << j;
}
node q[3];
q[0] = tk;
q[1] = node(ax,ay);
q[2] = node(bx,by);
int ano = step + 1;
if((en[0] == q[1] && en[1] == q[2]) || (en[0] == q[2] && en[1] == q[1]))
{
if(what == 0)
ans = min(ano,ans);
else
continue;
}
if(q[0] == q[1] || q[0] == q[2])
continue;
int temp = hash(tdir,q,dg);
int comp = find(temp);
if(comp == -1 || comp > ano)
{
if(comp == -1)
insert(temp,ano);
else
update(temp,ano);
Q.push(temp);
}
}
}
printf("%d\n",ans == inf?-1:ans);
}
int main()
{
cas = 0;
while(scanf("%d %d",&r,&c) == 2)
{
cas++;
int end = 0;
pcs = 0;
tot = 0;
for(int i = 0;i < r;i++)
for(int j = 0;j < c;j++)
{
char opt;
scanf(" %c",&opt);
mst[i][j] = opt;
switch(opt)
{
case 'A':
pa = node(i,j);
break;
case 'B':
pb = node(i,j);
break;
case 'K':
ki = node(i,j);
break;
case 'E':
en[end++] = node(i,j);
break;
case 'M':
pc[pcs++] = node(i,j);
break;
}
}
ans = inf;
scanf(" %c",&dir);
bfs();
}
}
å
backward sentence