这道题要逆向思维
反过来从大到小枚举， 就是在矩阵中一点一点加进去数字，这样比较
好操作， 如果正着做就要一点一点删除数字， 不好做。
我们需要在这个过程中维护联通块的个数， 这里用到了并查集。
首先加进去一个数， 联通分量数字先加一， 然后再考虑有没有和其他联通分量
相连。从当前位置四个方向枚举， 如果这个数之前已经被选中， 同时
不是一个联通分量， 那么也就是说当前这个木块把两个联通分量变成一个
联通分量， 联通分量数减去一。
这里还要把二维的化为一维的编号， 方便并查集操作。
然后注意这里输出很奇怪， 最后输出一行的最后一个位置是要有空格的
不然会格式错误。
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 1123456;
struct node
{int x, y, v;bool operator < (const node& rhs) const{return v < rhs.v;}
};
vector<node> nodes;
int a[MAXN], ans[MAXN], n, m, k, sum;
int vis[MAXN], f[MAXN];
int dir[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};int find(int x)
{if(f[x] != x)f[x] = find(f[x]);return f[x];
}inline int ID(int x, int y) { return x * m + y; } //二维化一维 void add(node u)
{sum++;vis[ID(u.x, u.y)] = 1;REP(i, 0, 4) //判断是否和其他联通分量相连 {int xx = u.x + dir[i][0], yy = u.y + dir[i][1];if(0 <= xx && xx < n && 0 <= yy && yy < m && vis[ID(xx, yy)]) //vis的作用是之前这个数有没有被选过 {int a = find(ID(u.x, u.y)), b = find(ID(xx, yy));if(a != b) sum--, f[a] = b;}}
}int main()
{int T;scanf("%d", &T);while(T--){memset(vis, 0, sizeof(vis));nodes.clear();scanf("%d%d", &n, &m);REP(i, 0, n)REP(j, 0, m){int v;scanf("%d", &v);nodes.push_back(node{i, j, v});}scanf("%d", &k);REP(i, 0, k) scanf("%d", &a[i]); sort(nodes.begin(), nodes.end()); //把点排序，这样加数比较方便 REP(i, 0, n * m) f[i] = i;int pos = nodes.size() - 1; sum = 0;for(int i = k - 1; i >= 0; i--){while(nodes[pos].v > a[i]) add(nodes[pos--]);ans[i] = sum;}REP(i, 0, k) printf("%d ", ans[i]); //注意最后一个数字后要有空格 printf("\n");}return 0;
}