E
  • 板块学术版
  • 楼主Forever1507
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/10/21 00:37
  • 上次更新2023/10/27 06:42:54
查看原帖
E
359614
Forever1507楼主2022/10/21 00:37

鬼故事,我写了个多起点bfs,用from[n*m+1]记答案,结果,只要我在bfs里更新答案并且在主函数里调用,就直接re(而且是在输入那里RE),如果我在bfs里注释所有维护答案的代码,或者在主函数里不调用答案都可以跑出来,这是什么原理?

#include<bits/stdc++.h>
using namespace std;
int t,n,m,ans;
char mp[400005];
int calc(int x,int y){
	return (x-1)*m+y;
}
int X(int x){
	return (x-1)/n+1;
}
int Y(int x){
	return (x%n==0)?n:x%n;
}
//struct node{
//	int v,w;
//};
int dis[400005],from[400005];
int dx[2]={1,-1};
bool vis[400005];
void bfs(){
//	cout<<"?????\n"; 
	queue<int>q;
	for(int i=1;i<=n*m;++i)dis[i]=1e9;
	for(int i=1;i<=n;++i)dis[calc(i,1)]=(mp[calc(i,1)]=='.'),q.push(calc(i,1));
	int mini=1e9;
	from[n*m+1]=1000000000;
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		int x=X(cur),y=Y(cur);
		if(vis[cur])continue;
		if(y==n){
			if(mini>dis[cur]){
				mini=dis[cur];
				from[n*m+1]=cur;
			}
			continue;
//			mini=min(mini,dis[cur]);
		}
		for(int i=0;i<=1;++i){
			int nx=x+1,ny=y+dx[i];
			if(nx<=0||ny<=0||nx>n||ny>m)continue;
			if(dis[calc(nx,ny)]){
				if(dis[calc(nx,ny)]>dis[cur]+(mp[calc(nx,ny)]=='.')){
					dis[calc(nx,ny)]=dis[cur]+(mp[calc(nx,ny)]=='.');
					from[calc(nx,ny)]=cur;
				}
			}
			else{
				dis[calc(nx,ny)]=dis[cur]+(mp[calc(nx,ny)]=='.');
				from[calc(nx,ny)]=cur;
				q.push(calc(nx,ny));
			}
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>t;
	while(t--){
		memset(vis,0,sizeof(vis));
		cin>>n>>m;
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				cin>>mp[calc(i,j)];
				if(mp[calc(i,j)]=='.')continue;
				if(i>=2)vis[calc(i-1,j)]=1;
				if(i<n)vis[calc(i+1,j)]=1;
				if(j>=2)vis[calc(i,j-1)]=1;
				if(j<m)vis[calc(i,j+1)]=1;
//				cout<<"???????\n";
			}
//			cout<<"dsjvisdbvjidsbv\n";
		}
//		cout<<"?!?!?!\n";
		bfs();
//		cout<<"dsvsdv\n";
		cout<<from[n*m-1+2]<<'\n';
		int K=0;//from[n*m-1+2];
		if(K==1e9)cout<<"NO\n";
		for(int i=1;i<=m;++i){
			mp[K]='#';
			K=from[K];
		} 
		cout<<"YES\n";
		for(int i=1;i<=n;++i){
			for(int j=1;j<=m;++j){
				cout<<mp[calc(i,j)];
			}
			cout<<'\n';
		}
	}
	return 0;
}

2022/10/21 00:37
加载中...