求助
查看原帖
求助
934977
lichengxi1楼主2024/1/22 10:43

#12 RE

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int MAXN = 1010;
int n,m,x1,y1,x2,y2,cnt[MAXN][MAXN],dx[9]={0,0,0,-1,1,-1,1,-1,1},dy[9]={0,-1,1,0,0,-1,-1,1,1};
char a[MAXN][MAXN];
bool vis[MAXN][MAXN],cup[MAXN][MAXN];
struct Node{
	int x,y;
};

void dfs(int x,int y,int d){
	cup[x][y] = 1;
	int tx = x + dx[d],ty = y + dy[d];
	if(tx>0&&tx<=n&&ty>0&&ty<=m&&a[tx][ty]!='X'&&!cup[tx][ty]) dfs(tx,ty,d);
}

void bfs(int sx,int sy,int tx,int ty){
	// 初始化
	queue<Node> q;
	memset(vis,0x00,sizeof(vis));
	memset(cup,0x00,sizeof(cup));
	memset(cnt,0x00,sizeof(cnt));
	// 奖杯分身
	for(int i = 1;i <= 8;++i) dfs(sx,sy,i);
	// 开始正式BFS
	q.push({tx,ty});
	vis[tx][ty] = 1,cnt[tx][ty] = 0;
	while(q.size()){
		int x = q.front().x,y = q.front().y;
		q.pop();
		if(cup[x][y]){
			cout << cnt[x][y] << endl;
			return ;
		}
		for(int i = 1;i <= 4;++i){
			int tux = x + dx[i],tuy = y + dy[i];
			if(tux>0&&tux<=n&&tuy>0&&tuy<=m&&a[tux][tuy]=='O'&&!vis[tux][tuy]){
				q.push({tux,tuy});
				vis[tux][tuy] = 1,cnt[tux][tuy] = cnt[x][y] + 1;
			}
		}
	}
	cout << "Poor Harry" << endl;
	return ;
}

int main(){
	cin >> n >> m;
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= m;++j) cin >> a[i][j];
	while(cin >> x1 >> y1 >> x2 >> y2){
		if(x1 == 0) return 0;
		bfs(x1,y1,x2,y2);
	}
	return 0;
}
2024/1/22 10:43
加载中...