求捞90 WA#6
查看原帖
求捞90 WA#6
946334
zyx15楼主2024/1/11 10:10
#include<bits/stdc++.h>
using namespace std;
int a[200][200],n,l1,r1,l2,r2,l,r,m,sum=INT_MAX,o,w,e;
char c;
bool vis[200][200];
int tx[4]={0,1,0,-1};//行 
int ty[4]={1,0,-1,0};//列 
struct re{
	int x,y,ans,f,p;
};
queue<re> q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]){
				vis[i][j]=vis[i-1][j]=vis[i][j-1]=vis[i-1][j-1]=1;
			}
		}
	}
	cin>>l1>>r1>>l2>>r2>>c;
	if(l1==l2&&r1==r2){
		cout<<0;
		return 0;
	}
	vis[l1][r1]=1;
	if(c=='E') o=0; else if(c=='S') o=1; else if(c=='W') o=2; else if(c=='N') o=3;
	q.push((re){l1,r1,0,o,0});
	while(!q.empty()){
		re x=q.front(); q.pop();
		if(x.x==l2&&x.y==r2){
			if(e%3==0) w=(x.p/3)+1;
			else w=(x.p/3)+1;
			sum=x.ans+w;
		}
		for(int i=0;i<=3;i++){
			l=x.x+tx[i]; r=x.y+ty[i]; e=x.p;
			if(l<n&&r>0&&r<m&&l>0&&!a[l][r]&&!vis[l][r]){
				vis[l][r]=1;
				if(i==x.f) q.push((re){l,r,x.ans,i,e+1});
				else if(x.x==l1&&x.y==r1&&i!=x.f){
					if(e%3==0) w=(e/3)+1;
					else w=(e/3)+2;
					q.push((re){l,r,x.ans+w+1,i,0});
				}
				else{
					if(e%3==0) w=(e/3)+1;
					else w=(e/3)+2;
					q.push((re){l,r,x.ans+w,i,0});
				} 
			}
		}
	}
	if(sum==INT_MAX){
		cout<<-1;
		return 0;
	}
	cout<<sum;
	return 0;
}/*
17 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16 4 4 16 N
第六个测试点
*/

求捞QAQ

2024/1/11 10:10
加载中...