1 条题解

  • 2
    @ 6 个月前

    这是一个经典的 广搜(bfs)题 用于寻找最短路

    一道很经典的题目 需要注意 搜索的时候不要越界

    Code:

    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #define int long long //个人习惯 有时候会死在数据范围上 直接从根源解决问题了
    
    using namespace std;
    const int N = 45;
    typedef pair<int , int> PII;
    
    int n , m;
    int g[N][N] , d[N][N];
    PII q[N * N]; // 模拟队列
    
    int bfs()
    {
        int hh = 0 , tt = 0; // hh是对头 tt队尾 
        q[0] = {0 , 0};
        memset(d , -1 , sizeof d);
        d[0][0] = 1;
    
        int dx[4] = {1 , 0 , -1 , 0} , dy[4] = {0 , 1 , 0 , -1};
    
        while (hh <= tt)
        {
            PII t = q[hh ++ ];
            for (int i = 0 ; i < 4 ; i ++ )
            {
                int x = t.first + dx[i] , y = t.second + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
                {
                    d[x][y] = d[t.first][t.second] + 1;
                    tt ++;
                    q[tt] = {x, y};
                }
            }
        }
    
        return d[n - 1][m - 1];
    }
    signed main()
    {
        cin >> n >> m;
    
        for (int i = 0 ; i < n ; i ++ )
        {
            for (int j = 0 ; j < m ; j ++ )
            {
                char ch;
                cin >> ch;
                if (ch == '.') g[i][j] = 0; // 转换为0 1 数组 后面更好记录长度
                else g[i][j] = 1;
            }
        }
    
        cout << bfs() << endl;
    
        return 0;
    }
    
    • 1

    信息

    ID
    1197
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    (无)
    递交数
    2
    已通过
    2
    上传者