CH2601:电路维修题解

思路

我们可以把整个电路系统想成是一个无向图,如果从点\(A(x_1,y_1)到B(x_2,y_2)\)且这个路上的方格的电路时符合走向的,那么认定这条路的边权为\(0\),如果与走向相悖,那么边权为\(1\)。为了做一个合理的优化,我们可以使用双端队列,优先处理边权为\(0\)的边,然后确保每个点只经过一次即可。复杂度比较低,看代码吧。

继续阅读CH2601:电路维修题解

POJ3322:Bloxorz I 题解

思路

这道题就是一道比较典型的 BFS 搜索题。我们可以先预处理好一些数组来帮助我们进行移动。使用一个结构体来存放每一个步骤的位置和方块躺下的方式,然后把它们放入队列中等待。这道题搞清楚位置的存放之后就应该比较清晰了。下面是代码:

继续阅读POJ3322:Bloxorz I 题解

P1141:01迷宫题解

思路

在我思考了很久之后(其实是理解题解),我解决了这道题的做法。主要就是并查集的一个扩展和预处理。我们在读取01迷宫时,就检测左边的点和右边的点是否连通。如果是连通的话,在并查集中合并,并且在并查集中把连通块个数相加即可

还有一个主要的思想就是映射。在并查集中我们的数组是一维的(mem[]),我们只需要一个计算函数把(x,y)转换成数字即可。(具体的:ret = x*n + y;)

代码

// P1141_ufs.cpp
#include <iostream>

using namespace std;

const int maxm = 10000000;
const int maxn = 1010;
char map[maxn][maxn];
int n, m;

struct UFS
{
    int mem[maxm];
    int mem_h[maxm];

    UFS()
    {
        for (int i = 0; i < maxm; i++)
            mem[i] = i, mem_h[i] = 1;
        for (int i = maxm; i < maxn; i++)
            mem_h[i] = 1;
    }

    int Find(int a)
    {
        if (mem[a] == a)
            return a;
        return mem[a] = Find(mem[a]);
    }

    void Unite(int a, int b)
    {
        if (Find(a) != Find(b))
            mem_h[Find(a)] += mem_h[Find(b)], mem[Find(b)] = Find(a);
    }
} u;

int hashcode(int a, int b)
{
    return a * n + b;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> map[i][j];
            // left;
            if (j != 1 && map[i][j - 1] != map[i][j])
                u.Unite(hashcode(i, j), hashcode(i, j - 1));
            // up;
            if (i != 1 && map[i - 1][j] != map[i][j])
                u.Unite(hashcode(i, j), hashcode(i - 1, j));
        }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        cout << u.mem_h[u.Find(hashcode(a, b))] << endl;
    }
    return 0;
}

代码我喜欢强格式化(vscode)所以行数可能比较多。