2 条题解

  • 1
    @ 2025-4-6 15:36:30
    using namespace std;
    #define LL long long
    #define down cout<<"\n";
    #define speed std::ios::sync_with_stdio(false)
    int dx[]={0,0,1,-1};
    int dy[]={1,-1,0,0};
    
    struct point{
    	int x;
    	int y;
    };
    
    const int N=1e5+5;
    int n,m;
    char ch[1005][1005];
    int vis[1005][1005];//保存步数
    int sx,sy;
    queue <point> q;
    
    int bfs(int x,int y){
    	point p{x,y};//起点
    	q.push(p);
    	while(!q.empty()){
    		p=q.front();
    		q.pop();
    		if(ch[p.x][p.y]=='T'){
    			return vis[p.x][p.y]-1;
    		}
    		for(int i=0;i<4;i++){
    			point np=p;
    			np.x+=dx[i];
    			np.y+=dy[i];
    			if(np.x>=0&& np.x<n && np.y>=0 && np.y<m && vis[np.x][np.y]==0 && ch[np.x][np.y]!='#'){
    				vis[np.x][np.y]=vis[p.x][p.y]+1;
    				q.push(np);
    			}
    		}
    	}
    	return 0;
    }
    
    int main(){
    	cin>>n>>m;
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			cin>>ch[i][j];
    			if(ch[i][j]=='S'){
    				sx=i;sy=j;
    			}
    		}
    	}
    	vis[sx][sy]=1;
    	int num=bfs(sx,sy);
    	if(!(num==0)){
    		cout<<num;
    	}
    	return 0;
    }
    
    

    信息

    ID
    244
    时间
    1000ms
    内存
    128MiB
    难度
    8
    标签
    (无)
    递交数
    61
    已通过
    11
    上传者