BFS #1#2 AC 其余MLE
查看原帖
BFS #1#2 AC 其余MLE
733515
LikablePie79015楼主2023/4/4 22:14
#include <iostream>
#include <cstdio>
#include <queue> 
using namespace std;

int r, c, cx, cy;
char a[120][120];
int road[120][120][2];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
queue <int> qx, qy;

void print(int x, int y){
	if(x == 1 && y == 1){
		printf("1 1\n");
		return ;
	}
	print(road[x][y][0], road[x][y][1]);
	printf("%d %d\n", x, y);
}

int main(){
	scanf("%d%d", &r, &c);
	for(int i = 1; i <= r; i++){
		for(int j = 1; j <= c; j++){
			cin >> a[i][j];
		}
	}
	
	qx.push(r);
	qy.push(c); 
	while(!qx.empty()){
		for(int i = 0; i < 4; i++){
			cx = qx.front() + dx[i];
			cy = qy.front() + dy[i];
			if(cx > 0 && cx <= r && cy > 0 && cy <= c  && a[cx][cy] != '*'){
				a[cx][cy] = '*';
				road[qx.front()][qy.front()][0] = cx;
				road[qx.front()][qy.front()][1] = cy;
				qx.push(cx);
				qy.push(cy);
			}
		}
		qx.pop();
		qy.pop();
		if(cx == r && cy == c) break;
	}
	
	print(r, c);
	return 0;
} 
2023/4/4 22:14
加载中...