1 条题解

  • 0
    @ 2024-1-9 20:30:33
    #include<bits/stdc++.h>
    using namespace std;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    struct node{
    	int x;
    	int y;
    	int step;
    };
    queue<node>q;
    int g[1011][1011];
    int main(){
    	int n,m,x,y,tx,ty,step;
    	char ch;
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>ch;
    			if(ch=='#') g[i][j]=1;
    		}
    	}
    	q.push(node{1,1,0});
    	g[1][1]=1;
    	while(!q.empty()){
    		x=q.front().x;y=q.front().y;step=q.front().step;
    		q.pop();
    		for(int i=0;i<4;i++){
    			tx=x+dx[i];
    			ty=y+dy[i];
    			if(tx>0&&tx<=n&&ty>0&&ty<=m&&g[tx][ty]==0){
    				q.push(node{tx,ty,step+1}); 
    				g[tx][ty]=1;
    				if(tx==n&&ty==m){
    					cout<<step+2<<endl;
    					return 0;
    				}
    			}
    		}
    	} 
    	return 0;
    }
    

    信息

    ID
    660
    时间
    1000ms
    内存
    128MiB
    难度
    2
    标签
    递交数
    115
    已通过
    39
    上传者