3 条题解

  • -1
    @ 2022-10-6 11:18:53
    #include <bits/stdc++.h>
    using namespace std;
    int n,m;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    struct temp 
    {
        int x,y,step;
    };
    queue<temp> q;
    char a[105][105];
    int vis[105][105];
    void bfs(int xx,int yy) 
    {
        while(!q.empty()) 
    	{
            temp k=q.front();
            if(a[k.x][k.y]=='T') 
    		{
                cout<<k.step<<endl;
                return ;
            }
            q.pop();
            if(vis[k.x][k.y])
            {
            	continue;
    		}       
            vis[k.x][k.y]=1;
            for(int i=0; i<4; i++) 
    		{
                int tx=k.x+dx[i],ty=k.y+dy[i];
                if(tx>=0&&ty>=0&&tx<n&&ty<m&&!vis[tx][ty]&&a[tx][ty]!='#') 
    			{
                    q.push({tx,ty,k.step+1});
                }
            }
        }
    }
    int main() 
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++) 
    	{
            cin>>a[i];
        }
        for(int i=0; i<n; i++) 
    	{
            for(int j=0; j<m; j++) 
    		{
                if(a[i][j]=='S') 
    			{
                    q.push({i,j,0});
                    bfs(i,j);
                    return 0;
                }
            }
        }
        return 0;
    }
    

    信息

    ID
    430
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    102
    已通过
    37
    上传者