1 solutions

  • 0
    @ 2022-3-25 14:35:59
    #include <stdio.h>
    #include <math.h>
    #include <algorithm>
    #include <iostream>
    #include <string.h>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <vector>
    using namespace std;
    int n,m;
    int dx[4]= {0,0,1,-1},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;
    }
    
    • 1

    Information

    ID
    770
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    6
    Tags
    # Submissions
    179
    Accepted
    51
    Uploaded By