36分求调
查看原帖
36分求调
911002
hjw100516楼主2024/7/9 20:23

请神犇们帮我看看

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=5e4+10;
int n,m,sx,sy,ex,ey,ans;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int ddx[8]={-1,-1,-1,0,1,1,1,0},ddy[8]={-1,0,1,1,1,0,-1,-1};
struct px{
	int x,y,s;
};
queue<px> q;
vector<char> mp[N];
vector<int> vis[N];
void bfs(int x,int y,int s){
	for(int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mp[xx][yy]=='O'&&vis[xx][yy]==INT_MAX){
			q.push({xx,yy,s+1});
			vis[xx][yy]=s+1;
		}
	}
	q.pop();
	if(!q.empty()) bfs(q.front().x,q.front().y,q.front().s);
}
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		mp[i].push_back('O');
		vis[i].push_back(0);
		for(int j=1;j<=m;j++){
			char a;
			cin>>a;
			mp[i].push_back(a);
			vis[i].push_back(0);
		}
	}
	scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
	while(sx||sy||ex||ey){
		if(sx==ex&&sy==ey){
			puts("0");
			scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
			continue;
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<=m;j++){
				vis[i][j]=INT_MAX;
			}
		}
		q.push({sx,sy,0});
		bfs(sx,sy,0);
		vis[sx][sy]=0;
		ans=vis[ex][ey];
		for(int i=0;i<8;i++){
			int xx=ex+ddx[i],yy=ey+ddy[i];
			while(xx>=1&&xx<=n&&yy>=1&&yy<=m&&mp[xx][yy]=='O'){
				ans=min(ans,vis[xx][yy]);
				xx+=ddx[i],yy+=ddy[i];
			}
		}
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=m;j++){
//				cout<<setw(15)<<vis[i][j];
//			}
//			puts("");
//		}
//		puts("");
		if(ans!=INT_MAX) printf("%d\n",ans);
		else puts("Poor Harry");
		scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
	}
	return 0;
}
2024/7/9 20:23
加载中...