CSL的校园卡

第一行为两个整数n,m(1 ≤ n, m ≤ 4)，表示地图的大小。接下来是n行m列的地图：X表示障碍物，S表示起点，O表示空地。障碍物不能直接经过，数据保证所有空地是可达的，起点有且只有一个。

C++11(clang++ 3.9) 解法, 执行用时: 42ms, 内存消耗: 14072K, 提交时间: 2019-10-29 22:48:35

#include<bits/stdc++.h>
using namespace std;

struct h
{
	int t,x1,y1,x2,y2,s;
}Q[999999];
bool V[5][5][5][5][(1<<16)+5]={0};
int main()
{
    int i,j,k,k1,k2,n,m,r,f,t,s,S=0,x1,y1,x2,y2,X1,Y1,X2,Y2;
    int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
    char R[5][5];
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)scanf("%s",R[i]);
	for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			if(R[i][j]=='S')Q[0].t=f=0,Q[0].x1=Q[0].x2=i,Q[0].y1=Q[0].y2=j,V[i][j][i][j][1<<(i*4+j)]=r=1,S+=(1<<(i*4+j)),Q[0].s=(1<<(i*4+j));
			if(R[i][j]=='O')S+=(1<<(i*4+j));
		}
	while(r!=f)
	{
		x1=Q[f].x1,y1=Q[f].y1,x2=Q[f].x2,y2=Q[f].y2,s=Q[f].s,t=Q[f++].t;
		if(s==S)break;
		for(i=0;i<4;i++)
		{
			X1=x1+dx[i],Y1=y1+dy[i];
			if(X1<0||X1>=n||Y1<0||Y1>=m||R[X1][Y1]=='X')continue;
			k1=(1<<(X1*4+Y1));
			for(j=0;j<4;j++)
			{
				X2=x2+dx[j],Y2=y2+dy[j];
				if(X2<0||X2>=n||Y2<0||Y2>=m||R[X2][Y2]=='X')continue;
				k2=(1<<(X2*4+Y2)),k=(k1|k2)|s;
				if(!V[X1][Y1][X2][Y2][k])V[X1][Y1][X2][Y2][k]=1,Q[r].x1=X1,Q[r].y1=Y1,Q[r].x2=X2,Q[r].y2=Y2,Q[r].s=k,Q[r++].t=t+1;
			}
		}
	}
	printf("%d\n",t);
	return 0;
}

详情