CF1438C 题解

#include<bits/stdc++.h>
using namespace std;
int t, n, m, a[105][105];
int dx[] = {0, 1, -1, 0, 0}, dy[] = {0, 0, 0, 1, -1};
int tid(int x, int y){
	return (x - 1) * m + y;
}
bool Invalid(int x, int y){
	if (x < 1 || y < 1 || x > n || y > m)
		return 1;
	else
		return 0;
}
vector<int> G[2000005], SCC[2000005];
int ig[2000005], dfn[2000005], low[2000005], col[2000005], vl[2000005];
int a1, a2, cnt, ign, ans, ccnt;
bool vis[2000005], vvis[2000005];
stack<int> s;
queue<int> q;
void tarjan(int u){
	dfn[u] = low[u] = ++cnt;
	s.push(u);
	vis[u] = 1;
	for (auto &v : G[u]){
		if (!dfn[v]){
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}else if (vis[v])
			low[u] = min(low[u], dfn[v]);
	}
	if (dfn[u] == low[u]){
		ccnt++;
		while (!s.empty()){
			int v = s.top();
			s.pop();
			vis[v] = 0;
			col[v] = ccnt;
			SCC[u].push_back(v);
			if (u == v)
				break;
		}
	}
}
void addedge(int u, int a, int v, int b){
	G[u + n * m * a].push_back(v + n * m * (b ^ 1));
	G[v + n * m * b].push_back(u + n * m * (a ^ 1));
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> t;
	while (t--){
		cin >> n >> m;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				cin >> a[i][j];
		for (int i = 1; i <= ccnt; i++)
			SCC[i].clear();
		for (int i = 1; i <= 2 * n * m; i++){
			G[i].clear();
			vis[i] = 0;
			col[i] = 0;
			low[i] = dfn[i] = 0;
		}
		cnt = ccnt = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++){
				for (int k = 1; k <= 4; k++){
					int nx = i + dx[k], ny = j + dy[k];
					if (Invalid(nx, ny))
						continue;
					if (a[nx][ny] == a[i][j]){
						int u, a, v, b;
						u = tid(i, j), v = tid(nx, ny);
						a = 1; b = 1;
						addedge(u, a, v, b);
						a = 0; b = 0;
						addedge(u, a, v, b);
					}else if (a[nx][ny] == a[i][j] + 1){
						int u, a, v, b;
						u = tid(i, j), v = tid(nx, ny);
						a = 0, b = 1;
						addedge(u, a, v, b);
					}else if (a[nx][ny] == a[i][j] - 1){
						int u, a, v, b;
						u = tid(i, j), v = tid(nx, ny);
						a = 1, b = 0;
						addedge(u, a, v, b);
					}
				}
			}
		for (int i = 1; i <= 2 * n * m; i++)
			if (!dfn[i])
				tarjan(i);
	//	for (int i = 1; i <= 2 * n * m; i++)
	//		cout << col[i] << " ";
	//	cout << "\n";
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++)
				cout << a[i][j] + (col[tid(i, j)] < col[tid(i, j) + n * m]) << " ";
			cout << "\n";
		}
	}
	return 0;
}