5 条题解

  • 1
    @ 2022-10-8 20:45:12
    #include<bits/stdc++.h>
    using namespace std; 
    struct oppo{
    	int x,y;
    	int s,f;
    }d[10086];
    
    char maps[105][105],b[105][105];
    int main(){
    	int n,m,x1,y1,x2,y2,head=1,tail=2;
    	bool flag=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
        	for(int j=1;j<=m;j++){
        		cin>>maps[i][j];
    		} 
    	}
    	//cin>>x1>>y1>>x2>>y2;
    	x1=1,y1=1;
    	x2=n,y2=m;
    	int tx,ty;
    	d[1].x=x1;
    	d[1].y=y1;
    	d[1].s=0;
    	b[d[1].x][d[1].y]=1;
    	d[1].f=0;
    	int moving[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
    	while(head<tail){
    		for(int i=0;i<=3;i++){
    			tx=d[head].x+moving[i][0];
    			ty=d[head].y+moving[i][1];
    			if(tx<1||tx>m||ty<1||ty>n||maps[tx][ty]=='#'||b[tx][ty]==1)
    			continue;
    			d[tail].x=tx;
    			d[tail].y=ty;
    			d[tail].s=d[head].s+1;
    			b[tx][ty]=1; 
    			d[tail].f=head;
    			tail++;
    		if(tx==x2&&ty==y2){
    		flag=1;
    		break;
    		}
    		}
    		if(flag==1)
    		break;
    		head++;
    	}
    	cout<<d[tail-1].s+1;
    	return 0;
    }
    

    信息

    ID
    429
    时间
    1000ms
    内存
    128MiB
    难度
    8
    标签
    递交数
    350
    已通过
    62
    上传者