不吸氧TLE,吸氧MLE
查看原帖
不吸氧TLE,吸氧MLE
353112
WTR2007楼主2021/8/10 20:33
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int w=0;
	char ch=getchar();
	while(ch>='0' && ch<='9'){
		w=(w<<1)+(w<<3)+ch-'0';
		ch=getchar();
	}
	return w;
}
char k;
int ex,ey,n,m,sum[55][55][5];
bool a[55][55],vis[55][55][5];
queue<int> q[3];
int bx[4]={-1,0,1,0};
int by[4]={0,1,0,-1};
void bfs(int x,int y,int de){
	q[0].push(x);
	q[1].push(y);
	q[2].push(de);
	vis[x][y][de]=1;sum[x][y][de]=0;
	while(!q[0].empty()){
		bool flag=0;
		int x1=q[0].front();q[0].pop();
		int y1=q[1].front();q[1].pop();
		int d1=q[2].front();q[2].pop();
		/*for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				for(int u=1;u<=4;u++){
					cout<<sum[i][j][u]<<" ";
				}
				cout<<"    ";
			}
			cout<<endl;
		}
		cout<<endl;*/
		int k;
		for(int i=1;i<=5;i++){
			if(i==4) k=d1;
			if(i<=3){
				if(flag) continue;
				int tx=x1+bx[d1-1]*i,ty=y1+by[d1-1]*i;
				if(tx<1||ty<1||tx+1>n||ty+1>m){
					flag=1;
					continue;
				}
				if(a[tx][ty+1]||a[tx+1][ty+1]||a[tx][ty]||a[tx+1][ty]){
					flag=1;
					continue;
				}
				if(!vis[tx][ty][d1]){
					vis[tx][ty][d1]=1;
					q[0].push(tx);
					q[1].push(ty);
					q[2].push(d1);
					sum[tx][ty][d1]=sum[x1][y1][d1]+1;
					if(tx==ex && ty==ey){
						cout<<sum[tx][ty][d1]-1<<endl;
						return ;
					}
				}
			}
			else{
				if(i==4){
					d1--;
					if(d1==0) d1=4;
				}
				else{
					d1+=2;
					if(d1==5) d1=1;
					if(d1==6) d1=2;
				}
				q[0].push(x1);
				q[1].push(y1);
				q[2].push(d1);
				sum[x1][y1][d1]=sum[x1][y1][k]+1;
			}
		}
	}
	printf("-1\n");
}
int main(){
	int x2,y2,l;
	n=read();m=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]=read();
		}
	}
	x2=read();y2=read();
	ex=read();ey=read();
	k=getchar();
	if(k=='N') l=1;
	else if(k=='E') l=2;
	else if(k=='S') l=3;
	else l=4;
	bfs(x2,y2,l);
	return 0;
}
2021/8/10 20:33
加载中...