萌新刚学OI,求调简单BFS
查看原帖
萌新刚学OI,求调简单BFS
133034
BetrayalObedience楼主2022/8/6 10:05
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,m,x1,y1,x2,y2,d;
int b[1001][5],aa[51][51][5],a[51][51];
char s;
int change(int d,int pd)
{
	if(!pd)
	{
		if(d==0) return 3;
		return d-1;
	}
	else
	{
		if(d==3) return 0;
		return d+1;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++)
	    {
	    	int t;
	    	cin>>t;
			if(t) a[i][j]=a[i-1][j]=a[i][j-1]=a[i-1][j-1]=1;	
		}
	cin>>x1>>y1>>x2>>y2>>s;
    if(s=='N') d=0;
    else if(s=='E') d=1;
    else if(s=='S') d=2;
    else d=3;
    int head=0,tail=1;
    aa[x1][y1][d]=1;
    b[1][0]=x1;
    b[1][1]=y1;
    b[1][2]=d;
    b[1][3]=0;
    while(head<=tail)
    {
    	head++;
    	int x=b[head][0],y=b[head][1],d=b[head][2],step=b[head][3];
    	if(x==x2&&y==y2)
    	{
    		cout<<step;
    		return 0;
		}
    	if(aa[x][y][change(d,0)]==0)
    	{
    		aa[x][y][change(d,0)]=1;
    		tail++;
    		b[tail][0]=x;
    		b[tail][1]=y;
    		b[tail][2]=change(d,0);
    		b[tail][3]=step+1;
		}
		if(aa[x][y][change(d,1)]==0)
		{
			aa[x][y][change(d,1)]=1;
			tail++;
			b[tail][0]=x;
			b[tail][1]=y;
			b[tail][2]=change(d,1);
			b[tail][3]=step+1;
		}
		for(int i=1;i<=3;i++)
		{
			if(i==1||i==2) 
			{
				if(d==0&&aa[x-i][y][d]==0&&x-i>=1&&a[x-i][y]==0&&a[x-1][y]==0)
	     		{
		     		aa[x-i][y][d]=1;
		    		tail++;
		    		b[tail][0]=x-i;
		    		b[tail][1]=y;
		    		b[tail][2]=d;
		    		b[tail][3]=step+1;
		    	}
			}
			else 
			{
				if(d==0&&aa[x-i][y][d]==0&&x-i>=1&&a[x-i][y]==0&&a[x-1][y]==0&&a[x-2][y]==0)
	     		{
		     		aa[x-i][y][d]=1;
		    		tail++;
		    		b[tail][0]=x-i;
		    		b[tail][1]=y;
		    		b[tail][2]=d;
		    		b[tail][3]=step+1;
		    	}
			}
			if(i==1||i==2)
			{
				if(d==1&&aa[x][y+i][d]==0&&y+i<m&&a[x][y+i]==0&&a[x][y+1]==0)
		    	{
		    		aa[x][y+i][d]=1;
		    		tail++;
		    		b[tail][0]=x;
		    		b[tail][1]=y+i;
		    		b[tail][2]=d;
		     		b[tail][3]=step+1;
		    	}
			}
			else 
			{
				if(d==1&&aa[x][y+i][d]==0&&y+i<m&&a[x][y+i]==0&&a[x][y+1]==0&&a[x][y+2]==0)
		    	{
		    		aa[x][y+i][d]=1;
		    		tail++;
		    		b[tail][0]=x;
		    		b[tail][1]=y+i;
		    		b[tail][2]=d;
		     		b[tail][3]=step+1;
		    	}
			}
			if(i==1||i==2)
			{
				if(d==2&&aa[x+i][y][d]==0&&x+i<n&&a[x+i][y]==0&&a[x+1][y]==0)
		    	{
		    		aa[x+i][y][d]=1;
		    		tail++;
		    		b[tail][0]=x+i;
		     		b[tail][1]=y;
		    		b[tail][2]=d;
		    		b[tail][3]=step+1;
		    	}
			}
			else
			{
				if(d==2&&aa[x+i][y][d]==0&&x+i<n&&a[x+i][y]==0&&a[x+1][y]==0&&a[x+2][y]==0)
		    	{
		    		aa[x+i][y][d]=1;
		    		tail++;
		    		b[tail][0]=x+i;
		     		b[tail][1]=y;
		    		b[tail][2]=d;
		    		b[tail][3]=step+1;
		    	}
			}
			if(i==1||i==2)
			{
				if(d==3&&aa[x][y-i][d]==0&&y-i>=1&&a[x][y-i]==0&&a[x][y-1]==0)
	    		{
	     			aa[x][y-i][d]=1;
		    		tail++;
		    		b[tail][0]=x;
		    		b[tail][1]=y-i;
		    		b[tail][2]=d;
		    		b[tail][3]=step+1;
		    	}
			}
			else 
			{
				if(d==3&&aa[x][y-i][d]==0&&y-i>=1&&a[x][y-i]==0&&a[x][y-1]==0&&a[x][y-2]==0)
	    		{
	     			aa[x][y-i][d]=1;
		    		tail++;
		    		b[tail][0]=x;
		    		b[tail][1]=y-i;
		    		b[tail][2]=d;
		    		b[tail][3]=step+1;
		    	}
			}
		}
	}
	cout<<-1;
}
2022/8/6 10:05
加载中...