题目

代码如下

#include <bits/stdc++.h>
using namespace std;
int n,m;
char a[30][30];
int book[30][30][30][30];
int spx,spy,shx,shy;
int ptx,pty,htx,hty;
struct node
{
	int hx,hy,px,py,step;
};
queue <node> q;
int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}},d1[4][2];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
			if(a[i][j]=='P')
			{
				spx=i,spy=j;
				a[i][j]='.';
			}
			if(a[i][j]=='H')
			{
				shx=i,shy=j;
				a[i][j]='.';
			}	
		}
	for(int i=0;i<4;i++)
	{
		char x;
		cin>>x;
		if(x=='N')
			d1[i][0]=-1,d1[i][1]=0;
		if(x=='S')
			d1[i][0]=1,d1[i][1]=0;
		if(x=='W')
			d1[i][0]=0,d1[i][1]=-1;
		if(x=='E')
			d1[i][0]=0,d1[i][1]=1;
	}
//BFS
	node t;
	t.px=spx;
	t.py=spy;
	t.hx=shx;
	t.hy=shy;
	t.step=0;
	book[spx][spy][shx][shy]=1;
	q.push(t);
	while(!q.empty())
	{
		node h=q.front();
		for(int i=0;i<4;i++)
		{
			ptx=h.px+d[i][0],pty=h.py+d[i][1];
			htx=h.hx+d1[i][0],hty=h.hy+d1[i][1];
			if(a[ptx][pty]=='!' || a[ptx][pty]=='#' || a[htx][hty]=='!')
				continue;
			if(book[ptx][pty][htx][hty]==1)
				continue;
			if(a[htx][hty]=='#')
				htx=h.hx,hty=h.hy;
			if(ptx==htx && pty==hty)
			{
				cout<<h.step+1;
				return 0;
			}
			if(htx==h.px && hty==h.py && ptx==h.hx && pty==h.hy)
			{
				cout<<h.step+1;
				return 0;
			}
			t.px=ptx;
			t.py=pty;
			t.hx=htx;
			t.hy=hty;
			t.step=h.step+1;
			book[ptx][pty][htx][hty]=1;
			if(t.step<=255)
				q.push(t);
		}
		q.pop();
	}
	cout<<"Impossible";
	return 0;
}

样例是对的，但一提交所有测试点 都内存超限了，求解决方法（bd上查了，但没找到合适的方法）