2011-0014
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
BFS[[BR]]
题意是给一张地图（最大10*10），上面有两个出口，一些石块，一些记忆碎片（不超过5个），三颗棋子（爱丽丝，镜像，骑士）。
棋子均不能出围墙[[BR]]
骑士面朝给定的方向每回合向前移动一步，如果不能向前移动，则转身（原地不动，消耗一回合）[[BR]]
爱丽丝每回合可向上下左右移动一步，且必须移动[[BR]]
镜像与爱丽丝的移动方向相反，移动一步（如果前方是棋子或石块或围墙则不移动）[[BR]]
只有爱丽丝可以捡记忆碎片[[BR]]
每回合移动顺序：爱丽丝 镜像 骑士[[BR]]
目标：爱丽丝捡起所有记忆碎片之后与镜像同一回合在出口上[[BR]]
注意：[[BR]]
1.爱丽丝与镜像均在出口上时迷宫解除，这一回合骑士来不及动[[BR]]
2.爱丽丝与镜像均在出口上时迷宫解除，不能继续捡记忆碎片[[BR]]
[[BR]]
本题的解法为BFS，状态数最多为10*10（爱丽丝的位置）*10*10（镜像的位置）*20（骑士的位置，最多有20种状态）*32（用二进制存储记忆碎片获得情况）=6400000[[BR]]
由于状态的总量较大，且组成状态的变量多，为了节省内存，可以将其压缩成一个变量[[BR]]
by luyi[[BR]]
{{{
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int O = 31;
char s[20][20],ss;
int map[20][20],f[10000][20][32],list[6400000],kx1[30],ky1[30],tk[30],len;
int m,n,tot,l,tt,kx,ky,ax,ay,bx,by,p,kk,dx,dy,t1,temp,te,flag,ta,tb;
//int pre[6400000],pret,last;
int bianma(int te,int k,int p)
{
return ((te+k*10000) << 5) + p;
}
void jiema(int k)
{
p = k & O;
k = k >> 5;
kk = f[te = (k % 10000)][temp = (k/10000)][p]+1;
tb = te % 100;
ta = te / 100;
by = tb % 10 + 1;
bx = tb / 10 + 1;
ay = ta % 10 + 1;
ax = ta / 10 + 1;
t1 = temp;
if ((++temp) == len) temp = 0;
kx = kx1[temp];
ky = ky1[temp];
}
void fangxiang(char s)
{
dx = dy = 0;
if (s == 'E') dy = 1; else
if (s == 'W') dy = -1; else
if (s == 'N') dx = -1; else
if (s == 'S') dx = 1;
}
int fff(char s,int x,int y)
{
if (s == '*') return 0;
if (s == 'R') return -1;
if (s == 'K') {kx = x;ky = y;return 0;}
if (s == 'A') {ax = x;ay = y;return 0;}
if (s == 'B') {bx = x;by = y;return 0;}
if (s == 'E') return -2;
if (s == 'M') {tot++;return (1<<(tot-1));}
}
void step()
{
kx1[len] = kx;
ky1[len++] = ky;
kx += dx;
ky += dy;
}
void walk()
{
while (map[kx][ky] != -1) step();
kx -= dx;
ky -= dy;
dx = -dx;
dy = -dy;
}
void knight()
{
kx1[0] = kx;
ky1[0] = ky;
len = 1;
fangxiang(ss);
kx += dx;
ky += dy;
walk();
walk();
while (!((kx == kx1[0])&&(ky == ky1[0]))) step();
for(int i = 0;i < len;i++) tk[i] = 10*kx1[i]+ky1[i]-11;
}
void work(int ax,int ay,int bx,int by,int p)
{
//pret = l-1;
if ((ax == bx)&&(ay == by)) return;
if (map[ax][ay] == -1) return;
if (map[ax][ay] > 0) p = (p | map[ax][ay]);
te = ax*1000+ay*100+bx*10+by - 1111;
if (f[te][temp][p] >= 0) return;
if ((ax == kx1[t1])&&(ay == ky1[t1])) return;
if ((bx == kx1[t1])&&(by == ky1[t1])) return;
if ((map[ax][ay] == -2)&&(map[bx][by] == -2))
{
if (p == tot)
{
flag = kk;
//last = tt+1;
l = tt + 1000;
} else
{
f[te][temp][p] = 0;
return;
}
}
if ((ax == kx)&&(ay == ky)) return;
if ((bx == kx)&&(by == ky)) return;
list[++tt] = bianma(te,temp,p);
//pre[tt] = pret;
f[te][temp][p] = kk;
}
//void print(int pret)
//{
// if (pret > 0) print(pre[pret]);
// jiema(list[pret]);
// printf("%d %d %d %d %d %d\n",ax,ay,bx,by,kx1[t1],ky1[t1]);
//}
void begin()
{
for(int i = 0;i < m;i++) scanf("%s",s[i]);
while (!isalpha(ss = getchar()));
memset(map,255,sizeof(map));
tot = 0;
for(int i = 0;i < m;i++)
for(int j = 0;j < n;j++)
map[i+1][j+1] = fff(s[i][j],i+1,j+1);
tot = (1 << tot) - 1;
knight();
memset(f,255,sizeof(f));
tt = l = 0;
list[tt] = bianma(te = ax*1000+ay*100+bx*10+by-1111,0,0);
f[te][0][0] = 0;
flag = -1;
while (tt >= l)
{
jiema(list[l]);
l++;
if (tb - ta != 10){
if ((map[bx-1][by] != -1)&&(tb - ta != 20)&&(tb - tk[t1] != 10))
work(ax+1,ay,bx-1,by,p);
else work(ax+1,ay,bx,by,p);}
if (ta - tb != 10){
if ((map[bx+1][by] != -1)&&(ta - tb != 20)&&(tk[t1] - tb != 10))
work(ax-1,ay,bx+1,by,p);
else work(ax-1,ay,bx,by,p);}
if (tb - ta != 1){
if ((map[bx][by-1] != -1)&&(tb - ta != 2)&&(tb - tk[t1] != 1))
work(ax,ay+1,bx,by-1,p);
else work(ax,ay+1,bx,by,p);}
if (ta - tb != 1){
if ((map[bx][by+1] != -1)&&(ta - tb != 2)&&(tk[t1] - tb != 1))
work(ax,ay-1,bx,by+1,p);
else work(ax,ay-1,bx,by,p);}
}
printf("%d\n",flag);
//if (flag > 0) print(last);
}
int main()
{
while(scanf("%d%d",&m,&n) != EOF) begin();
return 0;
}
}}}BFS
题意是给一张地图（最大10*10），上面有两个出口，一些石块，一些记忆碎片（不超过5个），三颗棋子（爱丽丝，镜像，骑士）。
棋子均不能出围墙
骑士面朝给定的方向每回合向前移动一步，如果不能向前移动，则转身（原地不动，消耗一回合）
爱丽丝每回合可向上下左右移动一步，且必须移动
镜像与爱丽丝的移动方向相反，移动一步（如果前方是棋子或石块或围墙则不移动）
只有爱丽丝可以捡记忆碎片
每回合移动顺序：爱丽丝 镜像 骑士
目标：爱丽丝捡起所有记忆碎片之后与镜像同一回合在出口上
注意：
1.爱丽丝与镜像均在出口上时迷宫解除，这一回合骑士来不及动
2.爱丽丝与镜像均在出口上时迷宫解除，不能继续捡记忆碎片
本题的解法为BFS，状态数最多为10*10（爱丽丝的位置）*10*10（镜像的位置）*20（骑士的位置，最多有20种状态）*32（用二进制存储记忆碎片获得情况）=6400000
由于状态的总量较大，且组成状态的变量多，为了节省内存，可以将其压缩成一个变量
by luyi
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int O = 31;
char s[20][20],ss;
int map[20][20],f[10000][20][32],list[6400000],kx1[30],ky1[30],tk[30],len;
int m,n,tot,l,tt,kx,ky,ax,ay,bx,by,p,kk,dx,dy,t1,temp,te,flag,ta,tb;
//int pre[6400000],pret,last;
int bianma(int te,int k,int p)
{
return ((te+k*10000) << 5) + p;
}
void jiema(int k)
{
p = k & O;
k = k >> 5;
kk = f[te = (k % 10000)][temp = (k/10000)][p]+1;
tb = te % 100;
ta = te / 100;
by = tb % 10 + 1;
bx = tb / 10 + 1;
ay = ta % 10 + 1;
ax = ta / 10 + 1;
t1 = temp;
if ((++temp) == len) temp = 0;
kx = kx1[temp];
ky = ky1[temp];
}
void fangxiang(char s)
{
dx = dy = 0;
if (s == 'E') dy = 1; else
if (s == 'W') dy = -1; else
if (s == 'N') dx = -1; else
if (s == 'S') dx = 1;
}
int fff(char s,int x,int y)
{
if (s == '*') return 0;
if (s == 'R') return -1;
if (s == 'K') {kx = x;ky = y;return 0;}
if (s == 'A') {ax = x;ay = y;return 0;}
if (s == 'B') {bx = x;by = y;return 0;}
if (s == 'E') return -2;
if (s == 'M') {tot++;return (1<<(tot-1));}
}
void step()
{
kx1[len] = kx;
ky1[len++] = ky;
kx += dx;
ky += dy;
}
void walk()
{
while (map[kx][ky] != -1) step();
kx -= dx;
ky -= dy;
dx = -dx;
dy = -dy;
}
void knight()
{
kx1[0] = kx;
ky1[0] = ky;
len = 1;
fangxiang(ss);
kx += dx;
ky += dy;
walk();
walk();
while (!((kx == kx1[0])&&(ky == ky1[0]))) step();
for(int i = 0;i < len;i++) tk[i] = 10*kx1[i]+ky1[i]-11;
}
void work(int ax,int ay,int bx,int by,int p)
{
//pret = l-1;
if ((ax == bx)&&(ay == by)) return;
if (map[ax][ay] == -1) return;
if (map[ax][ay] > 0) p = (p | map[ax][ay]);
te = ax*1000+ay*100+bx*10+by - 1111;
if (f[te][temp][p] >= 0) return;
if ((ax == kx1[t1])&&(ay == ky1[t1])) return;
if ((bx == kx1[t1])&&(by == ky1[t1])) return;
if ((map[ax][ay] == -2)&&(map[bx][by] == -2))
{
if (p == tot)
{
flag = kk;
//last = tt+1;
l = tt + 1000;
} else
{
f[te][temp][p] = 0;
return;
}
}
if ((ax == kx)&&(ay == ky)) return;
if ((bx == kx)&&(by == ky)) return;
list[++tt] = bianma(te,temp,p);
//pre[tt] = pret;
f[te][temp][p] = kk;
}
//void print(int pret)
//{
// if (pret > 0) print(pre[pret]);
// jiema(list[pret]);
// printf("%d %d %d %d %d %d\n",ax,ay,bx,by,kx1[t1],ky1[t1]);
//}
void begin()
{
for(int i = 0;i < m;i++) scanf("%s",s[i]);
while (!isalpha(ss = getchar()));
memset(map,255,sizeof(map));
tot = 0;
for(int i = 0;i < m;i++)
for(int j = 0;j < n;j++)
map[i+1][j+1] = fff(s[i][j],i+1,j+1);
tot = (1 << tot) - 1;
knight();
memset(f,255,sizeof(f));
tt = l = 0;
list[tt] = bianma(te = ax*1000+ay*100+bx*10+by-1111,0,0);
f[te][0][0] = 0;
flag = -1;
while (tt >= l)
{
jiema(list[l]);
l++;
if (tb - ta != 10){
if ((map[bx-1][by] != -1)&&(tb - ta != 20)&&(tb - tk[t1] != 10))
work(ax+1,ay,bx-1,by,p);
else work(ax+1,ay,bx,by,p);}
if (ta - tb != 10){
if ((map[bx+1][by] != -1)&&(ta - tb != 20)&&(tk[t1] - tb != 10))
work(ax-1,ay,bx+1,by,p);
else work(ax-1,ay,bx,by,p);}
if (tb - ta != 1){
if ((map[bx][by-1] != -1)&&(tb - ta != 2)&&(tb - tk[t1] != 1))
work(ax,ay+1,bx,by-1,p);
else work(ax,ay+1,bx,by,p);}
if (ta - tb != 1){
if ((map[bx][by+1] != -1)&&(ta - tb != 2)&&(tk[t1] - tb != 1))
work(ax,ay-1,bx,by+1,p);
else work(ax,ay-1,bx,by,p);}
}
printf("%d\n",flag);
//if (flag > 0) print(last);
}
int main()
{
while(scanf("%d%d",&m,&n) != EOF) begin();
return 0;
}