求助,bfs如何剪枝
查看原帖
求助,bfs如何剪枝
250607
toroso楼主2020/5/4 20:47
#pragma GCC optimize(3)
#include<stdio.h>
#include<cstring>
#include<iostream>
using namespace std;
inline int read(){
	int k=0,j=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')j=-1;c=getchar();}
	while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*j;
}
int a[55][55],ch[55][55];
int fx(char c){
	if(c=='E')return 1;
	if(c=='S')return 2;
	if(c=='W')return 3;
	if(c=='N')return 4;
}
int min(int a,int b){return a<b?a:b;}
long long ans;int n,m,x1,y1,y2,x2;
void bfs(int i,int j,int ff,int jsf,long long js){
	if(i==x2&&j==y2){ans=min(ans,js);return ;}
	if(i<1||i>=n||j<1||j>=m)return;
	if(jsf>=4)return;
	if(a[i][j]==1)return;
	if(js>=ans)return;
	switch(ff){
	    a[i][j]=1;
		case 1:{
			bfs(i,j,2,jsf+1,js+1);
			bfs(i,j,3,jsf+2,js+2);
			bfs(i,j,4,jsf+1,js+1);
			if(j<m-1&&a[i][j+1]==0)bfs(i,j+1,ff,0,js+1);
			if(j<m-2&&a[i][j+2]==0&&a[i][j+1]==0)
				bfs(i,j+2,ff,0,js+1);
			if(j<m-3&&a[i][j+3]==0&&a[i][j+2]==0&&a[i][j+
			1]==0)bfs(i,j+3,ff,0,js+1);
			break;
		}
		case 2:{
			bfs(i,j,3,jsf+1,js+1);
			bfs(i,j,4,jsf+2,js+2);
			bfs(i,j,1,jsf+1,js+1);
			if(i<n-1&&a[i+1][j]==0)bfs(i+1,j,ff,0,js+1);
			if(i<n-2&&a[i+2][j]==0&&a[i+1][j]==0)
				bfs(i+2,j,ff,0,js+1);
			if(i<n-3&&a[i+3][j]==0&&a[i+2][j]==0&&a[i+1]
			[j]==0)bfs(i+3,j,ff,0,js+1);
			break;
		}
		case 3:{
			bfs(i,j,2,jsf+1,js+1);
			bfs(i,j,1,jsf+2,js+2);
			bfs(i,j,4,jsf+1,js+1);
			if(j>1&&a[i][j-1]==0)bfs(i,j-1,ff,0,js+1);
			if(j>2&&a[i][j-2]==0&&a[i][j-1]==0)
				bfs(i,j-2,ff,0,js+1);
			if(j>3&&a[i][j-3]==0&&a[i][j-2]==0&&a[i][j-1]
			==0)bfs(i,j-3,ff,0,js+1);
			break;
		}
		case 4:{
			bfs(i,j,1,jsf+1,js+1);
			bfs(i,j,2,jsf+2,js+2);
			bfs(i,j,3,jsf+1,js+1);
			if(i>1&&a[i-1][j]==0)bfs(i-1,j,ff,0,js+1);
			if(i>2&&a[i-2][j]==0&&a[i-1][j]==0)
				bfs(i-2,j,ff,0,js+1);
			if(i>3&&a[i-3][j]==0&&a[i-2][j]==0&&a[i-1][j]
			==0)bfs(i-3,j,ff,0,js+1);
			break;
		}
		a[i][j]=0;
	}
}
int main(){
	n=read();m=read();ans=n*m;
	char c;
	memset(a,1,sizeof(a));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)ch[i][j]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(ch[i][j]==1)a[i-1][j]=1,a[i][j-1]=1,
				a[i-1][j-1]=1,a[i][j]=1;
			else a[i][j]=0;
	x1=read();y1=read();x2=read();y2=read();cin>>c;
	int cc=fx(c);
	if(a[x2][y2]==1){printf("-1");return 0;}
	bfs(x1,y1,cc,0,0);
	if(ans==n*m)printf("-1");
	else printf("%lld",ans);
	return 0;
}
2020/5/4 20:47
加载中...