BFS求助!!0分全MLE,样例没过
查看原帖
BFS求助!!0分全MLE,样例没过
486799
BlackPanda楼主2022/6/14 09:43
#include <bits/stdc++.h>
using namespace std;

struct Node{
	int x,y;
};

int rr,cc;
int xx[]={0,0,1,-1};
int yy[]={1,-1,0,0};
char mp[115][115];
int ans[115][115][2];

void bfs(int x,int y){
	queue<Node> q;
	Node r,f;
	r={x,y};
	q.push(r);
	while(!q.empty()){
		f=q.front();
		q.pop();
		if(f.x==rr && f.y==cc){
			return ;
		}
		for(int i=0;i<4;i++){
			int dx=f.x+xx[i];
			int dy=f.y+yy[i];
			if(dx<1 || dx>rr || dy<1 || dy>cc || mp[dx][dy]=='#')	continue;
			mp[dx][dy]='#';
			r={dx,dy};
			q.push(r);
			ans[dx][dy][0]=f.x;
			ans[dx][dy][1]=f.y;
		}
	}
}

void writeans(int x,int y){
	if(!ans[x][y][0] && !ans[x][y][1])	return ;
	writeans(ans[x][y][0],ans[x][y][1]);
	cout<<x<<" "<<y<<endl;
}

int main(){
	std::ios::sync_with_stdio(false);
	cin>>rr>>cc;
	for(int i=1;i<=rr;i++){
		for(int j=1;j<=cc;j++){
			cin>>mp[i][j];
		}
	}
	bfs(1,1);
	cout<<"1 1"<<endl;
	writeans(rr,cc);
	return 0;
}


2022/6/14 09:43
加载中...