2026-09-27 秋招XX笔试复盘：矩阵连通块与DFS状态
题目：两个01矩阵中的完全匹配区域
题目大意
给定两张最大为 的 01 矩阵，求 exact-match area 的个数。区域按上下左右四连通，要求两张图里的整块完全一致：位置都是 1，且不存在只在某一张图里向外延伸的部分。
我当时的想法
我从两张图都为 1 的位置开始搜。如果相邻位置出现一边是 1、一边是 0，这一块就不算完全匹配。
思路分析
把两张图中“至少有一张是 1”的格子放到同一张图里，按上下左右遍历连通块。
对一个这样的连通块，只要有一个位置两张图不同，它就不能算完全匹配。如果每个位置都相同，那么整块都是双 1，在两张图里也都没有额外伸出去的部分，答案加一。
这样，搜索只做两件事：访问完整个连通块，再记录这一块有没有不一致的位置。vis 表示这个格子已经处理过，设为真以后就不恢复。这里不需要当前路径状态。
即使已经发现不匹配，也要把整块走完。递归写法不能直接用 ok = ok && dfs(...)，因为 ok 为假时会短路，后面的格子就没有被标记。可以先调用 DFS，再合并返回值。下面直接用栈遍历，避免长连通块带来的递归深度问题。
每个格子最多入栈一次，时间、空间复杂度都是 。
参考代码
下面用栈遍历，两张矩阵的行列数相同。
#include <bits/stdc++.h>
using namespace std;
int countMatches(const vector<string>& a, const vector<string>& b) {
int n = a.size();
if (n == 0) return 0;
int m = a[0].size();
vector<vector<bool>> vis(n, vector<bool>(m, false));
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (vis[i][j] || (a[i][j] == '0' && b[i][j] == '0'))
continue;
bool ok = true;
vector<pair<int, int>> st = {{i, j}};
vis[i][j] = true;
while (!st.empty()) {
auto [x, y] = st.back();
st.pop_back();
if (a[x][y] != b[x][y]) ok = false;
for (int d = 0; d < 4; ++d) {
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= m)
continue;
if (vis[nx][ny]) continue;
if (a[nx][ny] == '0' && b[nx][ny] == '0')
continue;
vis[nx][ny] = true;
st.push_back({nx, ny});
}
}
if (ok) ++ans;
}
}
return ans;
}