思路
我们可以把整个电路系统想成是一个无向图,如果从点\(A(x_1,y_1)到B(x_2,y_2)\)且这个路上的方格的电路时符合走向的,那么认定这条路的边权为\(0\),如果与走向相悖,那么边权为\(1\)。为了做一个合理的优化,我们可以使用双端队列,优先处理边权为\(0\)的边,然后确保每个点只经过一次即可。复杂度比较低,看代码吧。
我们可以把整个电路系统想成是一个无向图,如果从点\(A(x_1,y_1)到B(x_2,y_2)\)且这个路上的方格的电路时符合走向的,那么认定这条路的边权为\(0\),如果与走向相悖,那么边权为\(1\)。为了做一个合理的优化,我们可以使用双端队列,优先处理边权为\(0\)的边,然后确保每个点只经过一次即可。复杂度比较低,看代码吧。
这道题就是一道比较典型的 BFS 搜索题。我们可以先预处理好一些数组来帮助我们进行移动。使用一个结构体来存放每一个步骤的位置和方块躺下的方式,然后把它们放入队列中等待。这道题搞清楚位置的存放之后就应该比较清晰了。下面是代码:
在我思考了很久之后(其实是理解题解),我解决了这道题的做法。主要就是并查集的一个扩展和预处理。我们在读取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)所以行数可能比较多。