P1141 01迷宫

本文主要是介绍P1141 01迷宫，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接

https://www.luogu.com.cn/problem/P1141

题目思路

一开始觉着是个宽搜就兴冲冲地背一了波模板，然后很高兴的TLE三个
所以这题需要优化，不能每个点都跑一边bfs，所以应该将连通块染色，相当于把一条路上的元素都标记成一样的，最后通过一个数组来存每个连通块的长度即可，并查集相同思想
这居然是一道橙题，可能是我太菜了

题目代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int g[N][N], idx[N][N], a[1000010];
int n, m;


int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
        {
            char c;
            cin >> c;
            g[i][j] = c - '0';
        }
        
    int d = 0;
    queue<PII> q;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
        {
            if(idx[i][j] == 0)
            {
                d ++ ;
                q.push({i, j});
                idx[i][j] = d;
                int cnt = 1;
                while(q.size())
                {
                    auto t = q.front();
                    q.pop();
                    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
                    for(int i = 0; i < 4; i ++ )
                    {
                        int a = t.first + dx[i], b = t.second + dy[i];
                        if(a >= 1 && a <= n && b >= 1 && b <= n && idx[a][b] == 0)
                        {
                            if(g[t.first][t.second] == 1 && g[a][b] == 0)
                            {
                                cnt ++ ;
                                idx[a][b] = d;
                                q.push({a, b});
                            }
                            if(g[t.first][t.second] == 0 && g[a][b] == 1)
                            {
                                cnt ++ ;
                                idx[a][b] = d;
                                q.push({a, b});
                            }
                        }
                    }
                }
                a[d] = cnt;
            }
        }
        
    while(m -- )
    {
        int x, y;
        cin >> x >> y;
        cout << a[idx[x][y]] << endl;
    }
    
    return 0;
}

这篇关于P1141 01迷宫的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！