90分,WA第九个,求调qwq
查看原帖
90分,WA第九个,求调qwq
993403
zhangchenxi666楼主2023/8/12 16:33
#include<bits/stdc++.h>
using namespace std;
int n,m,flag[60][60],fl,sx,sy,ex,ey;
int bx[4][3]={0,0,0,1,2,3,0,0,0,-1,-2,-3};
int by[4][3]={1,2,3,0,0,0,-1,-2,-3,0,0,0};
int mp[60][60],ans[60][60];
bool vis[60][60][10];
char fx;
//bool pd(int x,int y)
//{	
//	if(mp[x][y]||mp[x+1][y+1]||mp[x][y+1]||mp[x+1][y])
//		return false;
//	return true;
//}
void bfs(int x,int y){
	queue<pair<int,int> >q;
	memset(flag,0x3fff,sizeof flag);
	q.push(make_pair(x,y));
	flag[x][y]=fl;
	vis[x][y][flag[x][y]]=1;
	ans[x][y]=0;
	int sum;

	while(q.size()){
		int dx=q.front().first;
		int dy=q.front().second;
		q.pop();
		sum=ans[dx][dy]+1;
		for(int i=0;i<4;i++){
		
			int bs=abs(flag[dx][dy]-i);
			if(bs>2)bs=1;
			
			for(int j=0;j<3;j++){
				int nx=dx+bx[i][j];
				int ny=dy+by[i][j];	
				if(j==2){
					if(i==0){
						if(mp[nx][ny-1])continue;
					}
					if(i==1){
						if(mp[nx-1][ny])continue;
					}
					if(i==2){
						if(mp[nx][ny+1])continue;
					}
					if(i==3){
						if(mp[nx+1][ny])continue;	
					}
				}
				if(vis[nx][ny][flag[dx][dy]])continue;
		
				if(nx<=0||nx>=n||ny<=0||ny>=m||mp[nx][ny])break;
				
					flag[nx][ny]=i;
					if(ans[nx][ny]){
						int an=ans[nx][ny];
						ans[nx][ny]=min(sum+bs,an);
					}else ans[nx][ny]=sum+bs;
					vis[nx][ny][flag[dx][dy]]=1;
					q.push(make_pair(nx,ny));
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		cin>>mp[i][j];
		if(mp[i][j]==1){
			mp[i-1][j-1]=1;
			mp[i-1][j]=1;
			mp[i][j-1]=1;
		}
	}
	cin>>sx>>sy>>ex>>ey>>fx;
	if(fx=='E')fl=0;
	else if(fx=='S')fl=1;
	else if(fx=='W')fl=2;
	else if(fx=='N')fl=3;
	bfs(sx,sy);
//	for(int i=0;i<4;i++){
//		for(int j=0;j<3;j++)
//			cout<<bx[i][j];
//		cout<<endl;
//	}
//	for(int i=0;i<=n;i++){
//		for(int j=0;j<=m;j++)
//			cout<<ans[i][j]<<" ";
//		cout<<endl;
//	}
//	for(int i=0;i<=n;i++){
//		for(int j=0;j<=m;j++)
//			cout<<flag[i][j]<<" ";
//		cout<<endl;
//	}
	if(ex==sx&&ey==sy){
		cout<<0;
		return 0;
	}
	if(ans[ex][ey])cout<<ans[ex][ey];
	else cout<<-1;
}
2023/8/12 16:33
加载中...