狂奔的10分(回复@我)
查看原帖
狂奔的10分(回复@我)
959414
mjyhhhhh楼主2023/7/4 16:44
#include<bits/stdc++.h>
using namespace std;
int a[1005][1005],r,c,dx[]={0,-1,0,1},dy[]={-1,0,1,0},ax,ay,k=0;
char ch;
struct node{
	int x,y,step;
}; 
queue<node> q;
void dfs(int sx,int sy){
	q.push({sx,sy,0});
	a[sx][sy]=1;
	while(!q.empty()){
		//TODO
		int x=q.front().x;
		int y=q.front().y;
		int step=q.front().step;
		q.pop();
		if(x==ax&&y==ay){
			//TODO
			cout<<step<<endl;
			k=1;
			return;
		}
		else if(x==r&&y==c&&k==0){
			//TODO
			cout<<-1;
			return;
		}
		for(int i=0;i<4;i++){
			//TODO
			int tx=x+dx[i];
			int ty=y+dy[i];
			if(tx>=1&&tx<=r&&ty>=1&&ty<=c&&!a[tx][ty]){
				//TODO
				q.push({tx,ty,step+1});
				a[tx][ty]=1;
			}
		}
	}
}
int main(){
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		//TODO
		for(int j=1;j<=c;j++){
			//TODO
			cin>>ch;
			if(ch=='#'){
				ax=i;
				ay=j;
			}
			if(ch=='X'){
				a[i][j]=1;
			}
		}
	}
	dfs(1,1);
	return 0;
}
2023/7/4 16:44
加载中...