【最短路建图】迷宫

桃扇骨 2024-03-30 09:50 87阅读 0赞

[G-迷宫\_2022河南萌新联赛第（四）场：郑州轻工业大学 (nowcoder.com)][G-_2022_ _nowcoder.com]

题意：

![37f9ce0cbcf241b48add31212d1ce475.png][]

思路：

一眼最短路

对于最短路问题，难点在于建图，建完图之后只需要套板子即可

那么这道题我们如何建图？

结点是什么？就是格子

边是什么？相邻格子之间连边，一方有障碍就不连

边权是什么？边权一般按照题目最后要求的答案所定，答案是时间，那么我们设定边权的含义就是时间

这样我们就建完图了，当遇到花朵时，不贡献时间，跑一遍最短路即可

Code：

/*
    考察bfs
    一开始写dfs超时了
    说明这种map类型的搜索最好还是用bfs，dfs很容易超时
    map类型的搜索用pair类型存坐标
    还学到一个输入字符串的巧妙的方式
    */
    #include <bits/stdc++.h>
    using namespace std;
    const int mxn = 2010;
    int n, m;
    char g[mxn][mxn];
    int dist[mxn][mxn];
    bool st[mxn][mxn];
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    int main(){
        cin >> n >> m;
        for(int i = 1 ; i <= n ; i ++ ) cin >> g[i] + 1;
        
        memset(dist, 0x3f, sizeof dist);
        dist[1][1] = 0;
        st[1][1] = true;
        queue<pair<int, int>> q;
        q.push({1, 1});
        while(!q.empty()){
            auto tmp = q.front();
            q.pop();
            int x = tmp.first, y = tmp.second;
            st[x][y] = false;
            for(int i=0;i<4;i++){
                int a = x + dx[i], b = y + dy[i];
                //printf("*%d %d\n",x,y);
                if(a < 1 || a > n || b < 1 || b > m) continue;
                if(g[a][b] == '#') continue;
                if(dist[a][b] > dist[x][y] + (g[a][b] != '*')) 
                {
                    dist[a][b] = dist[x][y] + (g[a][b] != '*');
                    if(!st[a][b]) {
                        q.push({a, b});
                        st[a][b] = true;
                    }
                }
            }
        }
        int ans = dist[n][m];
        if(ans >= 0x3f3f3f3f) ans = -1;
        cout << ans << endl;
        return 0;
    }

**总结：**

**边权一般按照题目最后要求的答案所定**

[G-_2022_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/38487/G
[37f9ce0cbcf241b48add31212d1ce475.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/bb90375ead3444de919a2ca76d1754f7.png