10分求调
查看原帖
10分求调
400468
Aakkosetsumussa楼主2023/2/8 11:10
#include<bits/stdc++.h>
using namespace std;
typedef long long inr;
typedef unsigned long long unr;
typedef long double onr;
#define fr(y) for(inr i=1;i<=y;i++)
int n,m;
struct chessboard {
	int x,y,step;
} c;
queue<chessboard> q;
int a[5005][5005],vis[5007][5007];
int dx[7]= {0,1,0,-1},dy[7]= {1,0,-1,0};
char ch;
int bx,by,cx,cy;
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) {
			cin>>ch;
			if(ch=='O') a[i][j]=0;
			else a[i][j]=1;
		}
	while(cin>>bx>>by>>cx>>cy) {
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++) vis[i][j]=0;
		if(bx==0&&by==0&&cx==0&&cy==0) break;
		vis[cx][cy]=-1;
		
		int pa=cx,pb=cy;
		while(a[pa][pb]!=1&&pa<=n) vis[pa++][pb]=-1;
		pa=cx,pb=cy;
		while(a[pa][pb]!=1&&pb<=m) vis[pa][pb++]=-1;
		pa=cx,pb=cy;
		while(a[pa][pb]!=1&&pa>=1) vis[pa--][pb]=-1;
		pa=cx,pb=cy;
		while(a[pa][pb]!=1&&pb>=1) vis[pa][pb--]=-1;
		pa=cx,pb=cy;
		while(a[pa][pb]!=1&&pa<=n&&pb>=1) vis[pa++][pb--]=-1;
		pa=cx,pb=cy;
		while(a[pa][pb]!=1&&pb<=m&&pa<=n) vis[pa++][pb++]=-1;
		pa=cx,pb=cy;
		while(a[pa][pb]!=1&&pa>=1&&pb>=1) vis[pa--][pb--]=-1;
		pa=cx,pb=cy;
		while(a[pa][pb]!=1&&pb<=m&&pa>=1) vis[pa--][pb++]=-1;
		c.x=bx,c.y=by,c.step=0;
		q.push(c);
		bool fg=0;
		while(!q.empty()) {
			chessboard now=q.front();
			q.pop();
		//	cout<<now.x<<" "<<now.y<<" "<<now.step<<" "<<vis[now.x][now.y]<<endl;
			if(vis[now.x][now.y]!=-1) vis[now.x][now.y]=1;
			else {
				fg=1;
				cout<<now.step<<endl;
				break;
			}
			for(int i=0; i<4; i++) {
				int tx=now.x+dx[i],
				    ty=now.y+dy[i];
				if(0<tx&&tx<=n&&0<ty&&ty<=m&&vis[tx][ty]!=1&&a[tx][ty]!=1) {
					chessboard to;
					to.x=tx,to.y=ty,to.step=now.step+1;
					q.push(to);
				}
			}
		}
		if(fg==0) cout<<"Poor Harry\n";
	//*/
	}
	return 0;
}

思路是先把所有能直接看到的点标记出来,然后再搜到那些点的最短距离

2023/2/8 11:10
加载中...