【题解】sdoj3736[2018.08.07集训]B.箱子

用 dist[position][box1][box2][box3]记录人在 position，箱子 1 在 box1，箱子 2 在box2，箱子 3 在 box3 位置时最少需要花费的步数。 Bfs 一遍即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6e6+10;
bool vis[10][10];//标记是否可行 
char s[10];//读入每一行 
int nm[110][3];//新建图 
int R,C;//r行c列 
int sx,sy;//人的位置 
int cnt1,cnt2,cnt3;
//cnt1用来编号，cnt2cnt3为箱子和按钮的编号 
int nextx[4]={1,-1,0,0};
int nexty[4]={0,0,1,-1};//枚举四个方向 
int pos[10][10];//每个位置的编号 
int num[10][10];//地图的数字 
int box[5],button[5];//盒子与按钮的编号 
int f[50][50][50][50];//f[i][j][k][l]表示人在i，三个盒子在j,k,l时的最小步数 
int c[N][5];//c模拟队列 
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d%d",&R,&C);///R行C列 
	memset(nm,0,sizeof(nm));
	memset(f,255,sizeof(f));
	memset(num,0,sizeof(num));
	memset(box,0,sizeof(box));
	memset(button,0,sizeof(button));
	memset(vis,true,sizeof(vis));
	cnt1=cnt2=cnt3=0;
	for(int i=1;i<=R;i++)
	{
		scanf("%s",s);
		for(int j=1;j<=C;j++)
		{
			pos[i][j]=++cnt1;//给每个点标号 
			nm[cnt1][1]=i;nm[cnt1][2]=j;
			num[i][j]=s[j-1]-'0';//转成数字 
			if(num[i][j]==2)box[++cnt2]=pos[i][j];
			if(num[i][j]==3)button[++cnt3]=pos[i][j];
			if(num[i][j]==4)sx=i,sy=j,num[i][j]=0;
		}
	}
	f[pos[sx][sy]][box[1]][box[2]][box[3]]=0;//初始状态 
	c[1][0]=pos[sx][sy];//人的编号 
	c[1][1]=box[1];
	c[1][2]=box[2];
	c[1][3]=box[3]; //三个箱子 
	for(int i=1;i<=R;i++)
	for(int j=1;j<=C;j++)
	    if(num[i][j]==1)vis[i][j]=false; 
	for(int l=1,k=1;l<=k;l++)
	{
		int man=c[l][0],box1=c[l][1],box2=c[l][2],box3=c[l][3];
		int xman=nm[man][1],yman=nm[man][2];
		int xbox1=nm[box1][1],ybox1=nm[box1][2];
		int xbox2=nm[box2][1],ybox2=nm[box2][2];
		int xbox3=nm[box3][1],ybox3=nm[box3][2];
		vis[xbox1][ybox1]=vis[xbox2][ybox2]=vis[xbox3][ybox3]=false;
		if(box1==button[1]&&box2==button[2]&&box3==button[3])
		{
			printf("%d\n",f[man][box1][box2][box3]);
			return 0;
		}
		int step=f[man][box1][box2][box3];
		for(int i=0;i<4;i++)
		{
			int nxman=xman+nextx[i];
			int nyman=yman+nexty[i];//拓展一步 
			if(nxman>=1&&nxman<=R&&nyman>=1&&nyman<=C){
			    if(vis[nxman][nyman]&&f[pos[nxman][nyman]][box1][box2][box3]==-1)//这种状态没有走过 
			    {
				    f[pos[nxman][nyman]][box1][box2][box3]=step+1;
				    c[++k][0]=pos[nxman][nyman];
				    c[k][1]=box1;
				    c[k][2]=box2;
				    c[k][3]=box3;
			    }
			    int q[4]; 
				q[1]=box1;q[2]=box2;q[3]=box3;
			    if(pos[nxman][nyman]==q[2])swap(q[1],q[2]);
			    if(pos[nxman][nyman]==q[3])swap(q[1],q[3]);//避免状态重复
			    if(pos[nxman][nyman]==q[1])
			    {
				    int nnxman=xman+2*nextx[i];
				    int nnyman=yman+2*nexty[i];//沿当前方向再向前一步 
				    if(nnxman>=1&&nnxman<=R&&nnyman>=1&&nnyman<=C&&vis[nnxman][nnyman])
				    {
					    q[1]=pos[nnxman][nnyman];
					    for(int a=1;a<=3;a++)
					    for(int b=a+1;b<=3;b++)
					        if(q[b]!=0&&q[a]>q[b])swap(q[a],q[b]);
					    if(f[pos[nxman][nyman]][q[1]][q[2]][q[3]]==-1)
					    {
						    f[pos[nxman][nyman]][q[1]][q[2]][q[3]]=step+1;
						    c[++k][0]=pos[nxman][nyman];
						    c[k][1]=q[1];
						    c[k][2]=q[2];
						    c[k][3]=q[3];
					    }
				    }
			    } 
			}
			vis[xbox1][ybox1]=vis[xbox2][ybox2]=vis[xbox3][ybox3]=true;
	    }
	}
}

总结

bfs问题，最关键的是建模