自动搬运

查看原文

来自洛谷，原作者为

	曹老师 **

搬运于2025-08-24 21:50:43，当前版本为作者最后更新于2018-06-09 16:22:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

知识点：六维BFS

就一个bfs但是调了好几个小时（临界条件好麻烦

（虽然代码中有注释 但我还是想讲~~(tu)讲(cao)~~

因为有两头牛而且N值比较小 我们可以用六维数组模拟出每一个牛的朝向和位置

f[x1][y1][x2][t2][d1][d2]含义如上

还要注意临界条件：边界和障碍要判断 判断牛是否应该回到来时的点

然后就是进栈 更新什么的

这里我用了传址& 也可以直接Ctrl+C Ctrl+V来省事（不是复制My Code

接下来判断左转右转 特判一下方向：以免出负号RE

因为我们不知道最后的牛的脸朝哪儿 于是枚举方向即可求出答案

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<set>
#define MAXN 100005
#define LL long long
#define INF 2147483647
#define MOD 1000000007
#define free(s) freopen("s.txt","r",stdin);
#define lowbit(x) ((x&(-x))) 
#define debug(x) cout<<x<<endl;
using namespace std;
const int L=21;
int n,map[L][L],f[L][L][L][L][5][5],ans=INF,dx[]={0,-1,0,1,0},dy[]={0,0,1,0,-1};
bool vis[L][L][L][L][5][5];
struct node{
	int x1,x2,y1,y2,d1,d2;
    node (int x1,int y1,int x2,int y2,int d1,int d2):x1(x1),y1(y1),x2(x2),y2(y2),d1(d1),d2(d2) {}
    node () {}
};
int ex(char ch)
{
	if(ch=='E')
		return 1;
	return 0;
}
bool judge(int x,int y)
{
	return (x>=1)&&(x<=n)&&(y>=1)&&(y<=n);
}
void bfs()
{
	queue<node>q;
	q.push(node(n,1,n,1,1,2));
	while(!q.empty())
	{
		node head=q.front();
		q.pop();
		int nx1,nx2,ny1,ny2;		//直走 
		nx1=head.x1+dx[head.d1];
		ny1=head.y1+dy[head.d1];
		nx2=head.x2+dx[head.d2];
		ny2=head.y2+dy[head.d2];
		int cnt=f[head.x1][head.y1][head.x2][head.y2][head.d1][head.d2];
		if(!judge(nx1,ny1)||(!map[nx1][ny1]))//牛一不能直走 再回来 
			nx1=head.x1,ny1=head.y1;
		if(!judge(nx2,ny2)||(!map[nx2][ny2]))//牛二不能直走 再回来 
			nx2=head.x2,ny2=head.y2;
		if(head.x1==1&&head.y1==n)//牛一走到边界 不能移动 
			nx1=1,ny1=n;
        if (head.x2==1&&head.y2==n)//牛二走到边界 不能移动 
			nx2=1,ny2=n;
		int &p=f[nx1][ny1][nx2][ny2][head.d1][head.d2];
		if(p>cnt+1)//进栈 更新 
		{
			p=cnt+1;
			if(!vis[nx1][ny1][nx2][ny2][head.d1][head.d2])
			{
				vis[nx1][ny1][nx2][ny2][head.d1][head.d2]=1;
				q.push(node(nx1,ny1,nx2,ny2,head.d1,head.d2));
			}
		} 
		int d1,d2;
		d1=head.d1-1,d2=head.d2-1;		//左转 
		if(!d1) d1=4; if(!d2) d2=4;
		int &u=f[head.x1][head.y1][head.x2][head.y2][d1][d2];
		if(u>cnt+1)//进栈 更新 
		{
			u=cnt+1;
			if(!vis[head.x1][head.y1][head.x2][head.y2][d1][d2])
			{
				vis[head.x1][head.y1][head.x2][head.y2][d1][d2]=1;
				q.push(node(head.x1,head.y1,head.x2,head.y2,d1,d2));
			}
		}
        d1=head.d1+1,d2=head.d2+1;		//右转 
		if(d1==5) d1=1;if(d2==5) d2=1;
		int &r=f[head.x1][head.y1][head.x2][head.y2][d1][d2];
		if(r>cnt+1)//进栈 更新 
		{
			r=cnt+1;
			if(!vis[head.x1][head.y1][head.x2][head.y2][d1][d2])
			{
				vis[head.x1][head.y1][head.x2][head.y2][d1][d2]=1;
				q.push(node(head.x1,head.y1,head.x2,head.y2,d1,d2));
			}	
		}
	}
}
int main()
{
	memset(f,0x3f,sizeof(f));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			char c;
			cin>>c;
			map[i][j]=ex(c);
		}
	f[n][1][n][1][1][2]=0;
	bfs();
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			ans=min(ans,f[1][n][1][n][i][j]);//枚举最后的朝向 
	printf("%d",ans);
	return 0;
}