40分bfs求调
查看原帖
40分bfs求调
1088646
qqjjpp0011楼主2024/6/25 21:10
#include<bits/stdc++.h>
using namespace std;
const int M=10009;
bool vis[M][M];
char m[M][M];
int r,c,xa[M],ya[M],ans[M][M];
int mx[]={0,1,-1,0,0},my[]={0,0,0,1,-1};
struct Node{
    int x, y;
};
queue<Node> que;
void bfs() {
	que.push(Node{1,1});
	vis[1][1]=true;
	xa[1]=1;
	ya[1]=1;
	ans[1][1]=1;
    while(!que.empty()) {
        Node head = que.front(); que.pop();
        for(int i=1; i<=4; i++) {
           int dx = head.x + mx[i], dy = head.y + my[i];
            if(dx < 1 || dx>r || dy < 1 || dy>c || vis[dx][dy]==true) continue;
			ans[dx][dy]=ans[head.x][head.y]+1;
			vis[dx][dy] = true;
			xa[ans[dx][dy]]=dx;
			ya[ans[dx][dy]]=dy;
			if(dx==r&&dy==c&&ans[r][c]<=100000){
				for(int j=1;j<=ans[r][c];j++){
					cout<<xa[j]<<" "<<ya[j]<<endl;
				}
				return ;
			}
            que.push(Node{dx, dy});
		    } 
        }
    }
int main(){
    cin>>r>>c;
     for(int i=1;i<=r;i++){
     	for(int j=1;j<=c;j++){
     		cin>>m[i][j];
     		if(m[i][j]=='*'){
     			 vis[i][j]=true;
			 }
		 }
	 }
	 bfs();

    return 0;
}

2024/6/25 21:10
加载中...