#满屏红求调 样例过了
查看原帖
#满屏红求调 样例过了
539764
Hane_Eat_Fruit楼主2023/1/14 18:40
#include <bits/stdc++.h>
using namespace std;
int read() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
int r,c;
struct node{
	int x,y,step;
};
struct add{
	int x,y;
}vis[200][200];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
add ans[100005];
int cnt;
queue<node> q;
void print(int x,int y) {
	if(x==1&&y==1) return ;
	ans[++cnt]=vis[x][y];
	print(vis[x][y].x,vis[x][y].y);
	return ;
}
void bfs() {
	q.push(node{
		1,1,0
	});
	vis[1][1].x=1,vis[1][1].y=1;
	while(!q.empty()) {
		node t=q.front();
		q.pop();
		if(t.x==r&&t.y==c&&t.step<=100000){
			print(r,c);	
			break;
		}
		for(int i=0;i<4;i++) {
			int xx=dx[i]+t.x;
			int yy=dy[i]+t.y;
			if(vis[xx][yy].x==0&&vis[xx][yy].y==0&&xx>=1&&xx<=r&&yy>=1&&yy<=c) {
				q.push(node{
					xx,yy,t.step+1
				});
				vis[xx][yy].x=t.x,vis[xx][yy].y=t.y;
			}
		}
	}
	return ;
}
int main(){
	ios::sync_with_stdio(false);	
	r=read(),c=read();
	char x;
	for(int i=1;i<=r;i++) {
		for(int j=1;j<=c;j++) {
			cin>>x;
			if(x!='.') vis[i][j].x=-1,vis[i][j].y=-1;
		}
	}
	bfs(); 
	for(int i=cnt;i>=1;i--) {
		cout<<ans[i].x<<" "<<ans[i].y<<" "<<endl;
	}
	cout<<r<<" "<<c;
	return 0;
}
2023/1/14 18:40
加载中...