TLE5个点
查看原帖
TLE5个点
133116
Xhesika_Frost楼主2020/10/5 00:56

感觉和题解做法差不多啊

#include<iostream>
#include<queue>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
struct xy{
	int x;
	int y;
	int t;
};
queue <xy> q;
int vis[1001][1010];
char ma[1010][1010];
int mx[9]={0,1,1,1,0,-1,-1,-1};
int my[9]={1,1,0,-1,-1,-1,0,1};
int mx1[5]={0,1,0,-1};
int my1[5]={1,0,-1,0};
int n,m;
int xx,yy,xxx,yyy;
int f;
int cnt;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j)
		cin>>ma[i][j];
	}
	while(scanf("%d%d%d%d",&xx,&yy,&xxx,&yyy)){
		cnt++;
		if(!xx&&!yy&&!xxx&&!yyy){
			return 0;
		}
		f=0;
	//	memset(vis,0,sizeof(vis));
		vis[xx][yy]=cnt*2;
		for(int i=0;i<=7;++i){
			int u=xx+mx[i];
			int v=yy+my[i];
			while(ma[u][v]=='O'){
				vis[u][v]=cnt*2;;
				u+=mx[i];
				v+=my[i];
			}
		}
		if(vis[xxx][yyy]==cnt*2){
			cout<<0<<endl;
			continue;
		}
		while(!q.empty())
			q.pop();
		q.push(xy{xxx,yyy,0});
		while(!q.empty()){
			int u=q.front().x;
			int v=q.front().y;
			int ut=q.front().t;
		//	if(vis[u][v]==cnt*2){
		//		f=1;
		//		cout<<ut<<endl;
		//		break;
		//	}
			vis[u][v]=cnt*2-1;
			q.pop();
			for(int i=0;i<=3;++i){
				int u1=u+mx1[i];
				int v1=v+my1[i];
				if(vis[u1][v1]==cnt*2){
					f=1;
					cout<<ut+1<<endl;
					break;
				}
				else{
					if(ma[u1][v1]=='O'&&vis[u1][v1]!=cnt*2-1){
						vis[u][v]=cnt*2-1;
						q.push((xy){u1,v1,ut+1});
					}
					else{
						continue;
					}
				}	
			}
			if(f){
					break;
			}
		}
		if(!f){
			printf("Poor Harry\n");
		}	
	}
	return 0;
} 
2020/10/5 00:56
加载中...