3 solutions

  • 0
    @ 2022-3-24 23:00:57
    #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;
    char a[45][45];
    int vis[45][45];
    struct temp {
        int tx;
        int ty;
        int step;
    };
    int nx[4]= {0,0,1,-1};
    int ny[4]= {1,-1,0,0};
    queue<temp> q;
    void bfs() {
        while(!q.empty()) {
            temp t=q.front();
            q.pop();
            if(t.tx==n-1&&t.ty==m-1) {
                cout<<t.step;
                return;
            }
            if(vis[t.tx][t.ty])
                continue;
            vis[t.tx][t.ty]=1;
            for(int i=0; i<4; i++) {
                int x=t.tx+nx[i],y=t.ty+ny[i];
                if(x>=0&&y>=0&&x<n&&y<m&&vis[x][y]==0&&a[x][y]=='.')
                    q.push({x,y,t.step+1});
            }
        }
    }
    int main() {
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++) {
            cin>>a[i];
        }
        q.push({0,0,1});
        bfs();
        return 0;
    }
    

    Information

    ID
    769
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    7
    Tags
    # Submissions
    445
    Accepted
    88
    Uploaded By