鬼故事,我写了个多起点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;
}