20210915下午

最后一题，这怪物，他真的。。。怎么能这么猪鼻啊，我真的哭死。

T1	T2	T3	T4	T5
预测	100	100	100	100
一测	100	100	100	100

T1：

定义 f i , j f_{i,j} fi,j​和 g i , j g_{i,j} gi,j​分别表示两人到 i i i，时间为 j j j的情况是否存在，每次拓扑转移，初始 f 1 , 0 = g 1 , 0 = 1 f_{1,0}=g_{1,0}=1 f1,0​=g1,0​=1，最后从小到大判断 f n , i f_{n,i} fn,i​和 g n , i g_{n,i} gn,i​是否均为真就行。

T2：

简单搜索，不过题目实在是太恶心了，不给 n , m n,m n,m范围，不说虫能不能走8方向，终点放前面之类的。。。

预先把虫需要走到的地方预处理打标记可以省去每次判一遍能否打到。

T3：

理论 O ( n ! ) O(n!) O(n!)的搜索竟然能过，太扯了。。。

相同的存一下 c n t cnt cnt搜就行。

T4：

往一个方向走，能转就转，广搜就行。 v i s i , j , k vis_{i,j,k} visi,j,k​表示 k k k时刻在 ( i , j ) (i,j) (i,j)以剪枝。

T5：

最恶心的一道题，细节巨多，我调到第二天晚上才过。

有几个坑点：

1.怪物走只看曼哈顿距离，如果现有移动无法使曼哈顿距离缩短那他就不会动，这也是为啥这题怪物二倍速也追不到勇者，因为大部分情况都是

2.如果陷进陷阱里过了三步怪兽还没出来，不算再进陷阱。

3.只要两边格子右边有墙你就过不去，也就是会有 0 , 4 0,4 0,4这种相邻的格子。。。

4.勇者到了终点直接结束，不用管怪物。（有一个数据怪物守在终点上，你走过去过了。。。

除开这些，也就是一个很普通的搜索模拟了。

#include<bits/stdc++.h>
using namespace std;
const int N=55,fx[4]={-1,0,0,1},fy[4]={0,-1,1,0}; //按优先顺序
int n,m,d,sx,sy,tx,ty,ex,ey,dx,dy,s[N][N];
char Map[N][N],pr[4][10];
bool vis[N][N][N][N]; //人在(i,j)，怪在(k,l)，剪枝
struct node{
	int x,y,mx,my,s; //人位置，怪位置，步数
	int last,step; //上一步，这一步
	int drop;  //陷阱计时器
	bool leave;  //是否离开过陷阱，对应坑点2
}now,nxt,q[5000005];
bool in(int xx,int yy)
{
	if(xx>=1&&xx<=n&&yy>=1&&yy<=m) return true;
	else return false;
}
int abs(int x) {return x<0?-x:x;}
int dis(int xx,int xy,int yx,int yy) //曼哈顿距离
{
	return abs(xx-yx)+abs(xy-yy);
}
void print(node x)
{
	int s[N*N],tot=1;
	s[1]=x.step;
	for(int i=x.last;i!=1;i=q[i].last) //一直找上一步
	s[++tot]=q[i].step;
	for(int i=tot;i>=1;i--) puts(pr[s[i]]); //倒序输出
	printf("total steps: %d",x.s);
	return;
}
void bfs()
{
	now.x=sx;now.y=sy;now.mx=tx;now.my=ty;now.s=0;
	int h=1,t=1;q[1]=now;
	while(h<=t)
	{
		now=q[h++];
		if(vis[now.x][now.y][now.mx][now.my]) continue;
		vis[now.x][now.y][now.mx][now.my]=true;
		for(int i=0;i<4;i++)
		{
			nxt=now;nxt.s++;nxt.last=h-1;
			dx=now.x+fx[i];dy=now.y+fy[i];
			if((s[now.x][now.y]>>i)&1||(s[dx][dy]>>(i^3))&1) continue; //墙考虑两边，对应坑点3
			if(dx==ex&&dy==ey) {nxt.x=dx;nxt.y=dy;nxt.step=i;;print(nxt);return;} //要写在下一步前，对应坑点4
			if(!in(dx,dy)||Map[dx][dy]=='W'||(dx==nxt.mx&&dy==nxt.my)) continue;
			nxt.x=dx;nxt.y=dy;nxt.step=i;
			if(nxt.drop) {nxt.drop--;q[++t]=nxt;continue;}
			else{
				d=dis(nxt.x,nxt.y,nxt.mx,nxt.my);
				for(int i=1;i<5;i++)
				{
					dx=nxt.mx+fx[i%4];dy=nxt.my+fy[i%4];
					if((s[nxt.mx][nxt.my]>>(i%4))&1||(s[dx][dy]>>((i%4)^3))&1) continue;
					if(!in(dx,dy)) continue;
					if(dis(nxt.x,nxt.y,dx,dy)<d) {nxt.mx=dx;nxt.my=dy;nxt.leave=false;break;} //怪物只有能缩短才走，坑点1
				}
				if(Map[nxt.mx][nxt.my]=='W'&&!nxt.leave) {nxt.drop=3;nxt.leave=true;q[++t]=nxt;continue;}
			}
			if(nxt.mx==nxt.x&&nxt.my==nxt.y) continue;
			if(nxt.drop) {nxt.drop--;q[++t]=nxt;continue;}
			else{
				d=dis(nxt.x,nxt.y,nxt.mx,nxt.my);
				for(int i=1;i<5;i++)
				{
					dx=nxt.mx+fx[i%4];dy=nxt.my+fy[i%4];
					if((s[nxt.mx][nxt.my]>>(i%4))&1||(s[dx][dy]>>((i%4)^3))&1) continue;
					if(!in(dx,dy)) continue;
					if(dis(nxt.x,nxt.y,dx,dy)<d) {nxt.mx=dx;nxt.my=dy;nxt.leave=false;break;}
				}
				if(Map[nxt.mx][nxt.my]=='W'&&!nxt.leave) {nxt.drop=3;nxt.leave=true;q[++t]=nxt;continue;}
			}
			if(nxt.mx==nxt.x&&nxt.my==nxt.y) continue;
			if(vis[nxt.x][nxt.y][nxt.mx][nxt.my]) continue;
			q[++t]=nxt;
		}
	}
	printf("impossible");
	return;
}
int main()
{
	pr[0][0]='u';pr[0][1]='p';
	pr[1][0]='l';pr[1][1]='e';pr[1][2]='f';pr[1][3]='t';
	pr[2][0]='r';pr[2][1]='i';pr[2][2]='g';pr[2][3]='h';pr[2][4]='t';
	pr[3][0]='d';pr[3][1]='o';pr[3][2]='w';pr[3][3]='n';
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&s[i][j]);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",Map[i]+1);
		for(int j=1;j<=m;j++)
		{
			if(Map[i][j]=='S') sx=i,sy=j;
			if(Map[i][j]=='M') tx=i,ty=j;
			if(Map[i][j]=='E') ex=i,ey=j;
		}
	}
	bfs();
	return 0;
}
           

总结：搜索终于结束了。