Codechef11.6 MINESREV 一般图最大匹配
题目大意：
给定一张扫雷地图，其中某些位置是空格，某些位置是地雷。
如果对于某个空格，以这个空格为中心的$3\times{3}$区域内存在地雷，那么这个空格将被替换为一个数字方格，表示这个区域内存在地雷的个数。
正常的扫雷规则是：
点开一个空格，则能够同时点开这个空格所在的连通块以及这个连通块周围的一圈数字。
点开一个数字，则只能点开这个数字本身。
点开一个地雷，则只能点开这个地雷本身。
现在要将扫雷规则反过来：
令$s(x)$表示点开格子$x$能够同时点开的格子集合。
对于两个格子$p,q$，如果存在一个格子$x$使得$p\in{s(x)}$且$q\in{s(x)}$，则在新规则下点开$p$的同时也能点开$q$。
现在给定扫雷地图，求在新规则下最少多少次操作能够点开所有的格子。
数据范围：数据组数$T\leq{50}$，地图长宽$n,m\leq{50}$。
题解：
首先所有的地雷都必须点一次。
点开一个空格的话，能够点开这个空格所在的连通区域以及周围的一圈数字。
点开一个数字的话，能够点开所有与这个数字相邻的空格区域以及他们周围的一圈数字。
每个空格连通区域周围都一定有数字，那么点开空格肯定没有点开数字划算。
将每个空格连通区域以及周围的一圈数字看做一个点，每个同时与两个空格连通区域相邻的数字看做一条边，这样形成了一个无向图。
容易证明，每个数字最多只能与两个空格连通区域相邻。
实际上，问题抽象成了求一个无向图的最小边覆盖。
而这个答案等于点数减去最大匹配，我们利用一般图的最大匹配求解就行了。
还有一些孤立的数字，按照地雷处理。
无向图的点数是$O(nm)$级别的，而这个图显然是一个平面图，于是边数也是$O(nm)$级别的。
一种一般图最大匹配的实现能够做到$O(n^2m^2)$。
总时间复杂度$O(Tn^2m^2)$。
时空复杂度：
时间复杂度$O(Tn^2m^2)$，空间复杂度$O(nm)$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Solver {
static const int V = 510;
static const int E = 250010;
int n, fa[V];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int head[V], nxt[E], to[E], ind;
int nextv[V], match[V], mark[V], vis[V];
bool g[V][V];
void reset() {
ind = 0;
memset(head, 0, sizeof head);
memset(match, -1, sizeof match);
memset(g, 0, sizeof g);
}
void addedge(int a, int b) {
int q = ++ind;
to[q] = b;
nxt[q] = head[a];
head[a] = q++;
}
void make(int a, int b) {
if (!g[a][b]) {
g[a][b] = g[b][a] = 1;
//printf("%d %d\n", a, b);
addedge(a, b);
addedge(b, a);
}
}
int q[V], fr, ta;
int get_lca(int x, int y) {
static int tclock;
++tclock;
while (1) {
if (x != -1) {
x = find(x);
if (vis[x] == tclock)
return x;
vis[x] = tclock;
if (match[x] == -1)
x = -1;
else
x = nextv[match[x]];
}
swap(x, y);
}
}
void compress(int x, int lca) {
int y, z;
while (x != lca) {
y = match[x];
z = nextv[y];
if (mark[y] == 1)
mark[q[ta++] = y] = 0;
if (find(z) != lca)
nextv[z] = y;
fa[find(x)] = fa[find(y)] = find(z);
x = z;
}
}
bool augment(int s) {
int i, j, x, y, z;
for (i = 1; i <= n; ++i) {
nextv[i] = -1;
fa[i] = i;
mark[i] = -1;
}
fr = ta = 0;
mark[q[ta++] = s] = 0;
while (fr != ta) {
x = q[fr++];
for (j = head[x]; j; j = nxt[j]) {
y = to[j];
if (match[x] == y || find(x) == find(y) || mark[y] == 1)
continue;
if (mark[y] == 0) {
z = get_lca(x, y);
if (find(x) != z)
nextv[x] = y;
if (find(y) != z)
nextv[y] = x;
compress(x, z);
compress(y, z);
}
else if (match[y] == -1) {
nextv[y] = x;
while (y != -1) {
x = nextv[y];
z = match[x];
match[x] = y;
match[y] = x;
y = z;
}
return 1;
}
else {
nextv[y] = x;
mark[q[ta++] = match[y]] = 0;
mark[y] = 1;
}
}
}
return 0;
}
int maxMatch() {
int ans = 0;
for (int i = 1; i <= n; ++i)
if (match[i] == -1)
ans += augment(i);
return ans;
}
}g;
#define N 60
char s[N][N];
int id, bel[N][N];
static const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
static const int dy[] = {0, -1, 1, -1, 1, -1, 0, 1};
void dfs(int x, int y, int _id) {
bel[x][y] = _id;
for (int k = 0; k < 8; ++k) {
if (s[x + dx[k]][y + dy[k]] == '.' && !bel[x + dx[k]][y + dy[k]])
dfs(x + dx[k], y + dy[k], _id);
}
}
int main() {
//freopen("tt.in", "r", stdin);
int T;
cin >> T;
int n, m, i, j, k;
while (T--) {
scanf("%d%d", &n, &m);
memset(s, 0, sizeof s);
for (i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
int cnt;
for (i = 1; i <= n; ++i) {
for (j = 1; j <= m; ++j) {
if (s[i][j] == '.') {
cnt = 0;
for (k = 0; k < 8; ++k)
cnt += s[i + dx[k]][j + dy[k]] == '*';
if (cnt > 0)
s[i][j] = '0' + cnt;
}
}
}
id = 0;
memset(bel, 0, sizeof bel);
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
if (s[i][j] == '.' && !bel[i][j])
dfs(i, j, ++id);
/*for (i = 1; i <= n; ++i) {
for (j = 1; j <= m; ++j)
putchar(s[i][j]);
puts("");
}
puts("");
for (i = 1; i <= n; ++i) {
for (j = 1; j <= m; ++j)
printf("%02d", bel[i][j]);
puts("");
}*/
g.reset();
g.n = id;
int ans = 0;
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
ans += s[i][j] == '*';
vector<int> sav, _sav;
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j) {
//printf("%d %d\n", i, j);
if (s[i][j] != '.' && s[i][j] != '*') {
sav.clear();
for (k = 0; k < 8; ++k)
if (s[i + dx[k]][j + dy[k]] == '.')
sav.push_back(bel[i + dx[k]][j + dy[k]]);
if (sav.size())
sort(sav.begin(), sav.end());
_sav.clear();
for (k = 0; k < sav.size(); ++k)
if (k == 0 || sav[k] != sav[k - 1])
_sav.push_back(sav[k]);
if (_sav.size() == 0)
++ans;
else if (_sav.size() == 2)
g.make(_sav[0], _sav[1]);
}
}
ans += id - g.maxMatch();
printf("%d\n", ans);
}
return 0;
}
Jan 24, 2023 08:03:32 PM
With this topic, we are presented with an interesting challenge - to reverse the typical rules of Minesweeper. The goal is to find the minimum number of operations to open peter veres photography work all the grids under the new rules. To achieve this, we must consider the 3x3 area around each space, and any connected blocks and number squares that can be opened simultaneously. With careful thought and analysis, we can solve this puzzle and unlock new possibilities!