30分MLE+WA求助
查看原帖
30分MLE+WA求助
785636
2022_37_yzyUUU楼主2024/11/27 18:48
#include<bits/stdc++.h>
using namespace std;
int n,m,bx,by,ex,ey,ans=INT_MAX;
char g[105][105];
int vis[105][105],gk[105][105];
int xx[]={0,1,-1,0,0};
int yy[]={0,0,0,1,-1};
void bfs(){
	deque<int> x,y,k,l;
	x.push_front(bx);y.push_front(by);
	k.push_front(-1);l.push_front(-1);
	vis[bx][by]=1;memset(gk,0x3f3f3f,sizeof(gk));
	gk[bx][by]=0;
	while(x.size()){
		int tx=x.front(),ty=y.front();
		int tk=k.front(),tl=l.front();
		x.pop_front(),y.pop_front(),k.pop_front(),l.pop_front();
		if(tx==ex&&ty==ey){
			ans=min(ans,tk);
		}
		for(int i=1;i<=4;i++){
			int dl=tl,dk=tk,dx=tx+xx[i],dy=ty+yy[i];
			if(dx<1||dy<1||dx>n||dy>m||g[dx][dy]=='*'||gk[dx][dy]<gk[tx][ty]+1)continue;
			if(i!=tl){
				dk++;
				dl=i;gk[dx][dy]=dk;
				x.push_back(dx),y.push_back(dy);
				k.push_back(dk),l.push_back(dl);
			}else{
				gk[dx][dy]=dk;
				x.push_back(dx),y.push_back(dy);
				k.push_back(dk),l.push_back(dl);
			}
		}
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
			if(g[i][j]=='C'){
				if(bx==0||by==0)
					bx=i,by=j;
				else 
					ex=i,ey=j;
			}
		}
	}
	bfs();
	cout<<ans;
}
2024/11/27 18:48
加载中...