求助各路神仙!思路BFS,去重,爆搜。
查看原帖
求助各路神仙!思路BFS,去重,爆搜。
967856
PeaceSunset楼主2023/8/10 17:14

在线等,挺急的。

#include<bits/stdc++.h>
using namespace std;

int a,b;
char wall[510][510];
int dis[510][510];

struct node{
	int x;
	int y;
};

deque<node> q;
queue<node> p;

void bfs_end(int t,int o){
	node r;
	r.x=t,r.y=o;
	p.push(r);
	while(p.size()){
		int k=p.front().x,l=p.front().y;
		p.pop();
		if(wall[k][l]=='\\'&&k-1>=0&&l-1>=0&&dis[k-1][l-1]==-5){
			dis[k-1][l-1]=-1;
			node w;
			w.x=k-1,w.y=l-1;
			p.push(w);
		}
		if(wall[k][l+1]=='/'&&k-1<=a&&l+1>=0&&dis[k-1][l+1]==-5){
			dis[k-1][l+1]=-1;
			node w;
			w.x=k-1,w.y=l+1;
			p.push(w);
		}
		if(wall[k+1][l+1]=='\\'&&k+1<=a&&l+1<=b&&dis[k+1][l+1]==-5){
			dis[k+1][l+1]=-1;
			node w;
			w.x=k+1,w.y=l+1;
			p.push(w);
		}
		if(wall[k+1][l]=='/'&&k+1<=a&&l-1>=0&&dis[k+1][l-1]==-5){
			dis[k+1][l-1]=-1;
			node w;
			w.x=k+1,w.y=l-1;
			p.push(w);
		}
	}
}

void bfs_start(int i,int j){
	node r;
	r.x=i,r.y=j;
	q.push_front(r);
	while(q.size()){
		int k=q.front().x,l=q.front().y;
		q.pop_front();
		if(wall[k][l]=='\\'&&k-1>=0&&l-1>=0&&dis[k-1][l-1]==-5){
			dis[k-1][l-1]=dis[k][l];
			node w;
			w.x=k-1,w.y=l-1;
			q.push_front(w);
		}else if(k-1>=0&&l-1>=0&&dis[k-1][l-1]==-5){
			dis[k-1][l-1]=dis[k][l]+1;
			node w;
			w.x=k-1,w.y=l-1;
			q.push_back(w);
		}
		if(wall[k][l+1]=='/'&&k-1<=a&&l+1>=0&&dis[k-1][l+1]==-5){
			dis[k-1][l+1]=dis[k][l];
			node w;
			w.x=k-1,w.y=l+1;
			q.push_front(w);
		}else if(k-1<=a&&l+1>=0&&dis[k-1][l+1]==-5){
			dis[k-1][l+1]=dis[k][l]+1;
			node w;
			w.x=k-1,w.y=l+1;
			q.push_back(w);
		}
		if(wall[k+1][l+1]=='\\'&&k+1<=a&&l+1<=b&&dis[k+1][l+1]==-5){
			dis[k+1][l+1]=dis[k][l];
			node w;
			w.x=k+1,w.y=l+1;
			q.push_front(w);
		}else if(k+1<=a&&l+1<=b&&dis[k+1][l+1]==-5){
			dis[k+1][l+1]=dis[k][l]+1;
			node w;
			w.x=k+1,w.y=l+1;
			q.push_back(w);
		}
		if(wall[k+1][l]=='/'&&k+1<=a&&l-1>=0&&dis[k+1][l-1]==-5){
			dis[k+1][l-1]=dis[k][l];
			node w;
			w.x=k+1,w.y=l-1;
			q.push_front(w);
		}else if(k+1<=a&&l-1>=0&&dis[k+1][l-1]==-5){
			dis[k+1][l-1]=dis[k][l]+1;
			node w;
			w.x=k+1,w.y=l-1;
			q.push_back(w);
		}
		if(dis[k-1][l-1]==-1&&wall[k][l]=='\\'||dis[k-1][l+1]==-1&&wall[k][l+1]=='/'||dis[k+1][l+1]==-1&&wall[k+1][l+1]=='\\'||dis[k+1][l-1]==-1&&wall[k+1][l]=='/'){
			cout << dis[k][l];
			return;
		}else if(dis[k-1][l-1]==-1||dis[k-1][l+1]==-1||dis[k+1][l+1]==-1||dis[k+1][l-1]==-1){
			cout << dis[k][l]+1;
			return;
		}
	}
}

int main(){
	cin >> a >> b;
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			cin >> wall[i][j];
		}
	}
	memset(dis,-5,sizeof dis);
	bfs_end(a,b);
	bfs_start(0,0);
	return 0;
}

输不出来怎么办?求助大佬。

2023/8/10 17:14
加载中...