求助,TLE on #8
查看原帖
求助,TLE on #8
511907
一只大龙猫楼主2021/11/16 14:44

RT,看了一下题解,感觉自己的思路好像和题解没有什么不同。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct node{
	int x,y,t;
}; 
queue<node> q;
char c[600][600];
int n,m,ans,startx,starty,compx,compy,endx,endy;
bool vis[600][600],okcomp,okend;
int main(){
	memset(c,'#',sizeof(c));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
			if(c[i][j]=='S'){
				startx=i;
				starty=j;
			}
			if(c[i][j]=='C'){
				compx=i;
				compy=j;
			}
			if(c[i][j]=='G'){
				endx=i;
				endy=j;
			}
		}
	}
	q.push((node){startx,starty,0});
	while(!q.empty()){
		node p=q.front();
		q.pop();
		if(p.x==compx&&p.y==compy){
			ans+=p.t;
			okcomp=1;
			break;
		}
		vis[p.x][p.y]=1;
		if(c[p.x+1][p.y]!='#'&&!vis[p.x+1][p.y]){
			q.push((node){p.x+1,p.y,p.t+1});
		}
		if(c[p.x][p.y+1]!='#'&&!vis[p.x][p.y+1]){
			q.push((node){p.x,p.y+1,p.t+1});
		}
		if(c[p.x-1][p.y]!='#'&&!vis[p.x-1][p.y]){
			q.push((node){p.x-1,p.y,p.t+1});
		}
		if(c[p.x][p.y-1]!='#'&&!vis[p.x][p.y-1]){
			q.push((node){p.x,p.y-1,p.t+1});
		}
	}
	if(!okcomp){
		cout<<"-1"<<endl;
		return 0;
	}
	while(!q.empty())q.pop();
	memset(vis,0,sizeof(vis));
	q.push((node){compx,compy,0});
	while(!q.empty()){
		node p=q.front();
		q.pop();
		if(p.x==endx&&p.y==endy){
			ans+=p.t;
			okend=1;
			break;
		}
		vis[p.x][p.y]=1;
		if(c[p.x+1][p.y]!='#'&&!vis[p.x+1][p.y]){
			q.push((node){p.x+1,p.y,p.t+1});
		}
		if(c[p.x][p.y+1]!='#'&&!vis[p.x][p.y+1]){
			q.push((node){p.x,p.y+1,p.t+1});
		}
		if(c[p.x-1][p.y]!='#'&&!vis[p.x-1][p.y]){
			q.push((node){p.x-1,p.y,p.t+1});
		}
		if(c[p.x][p.y-1]!='#'&&!vis[p.x][p.y-1]){
			q.push((node){p.x,p.y-1,p.t+1});
		}
	}
	if(!okend){
		cout<<"-1";
	}else{
		cout<<ans;
	}
	cout<<endl;
	return 0;
}
2021/11/16 14:44
加载中...