Educational Codeforces Round 174 (Rated for Div. 2)

Problem - B - Codeforces

之前没思路，我看了看答案。

思路不就来了：

简而言之，BFS那样遍历周围（上下左右均一次），如果有同色，就把这部分相邻的隔开，可以得到两块陌生人集合，就能解决，

每种颜色，最少要1次变换，最多要两次变换。

在写之前，我再优化一下：在录入当前颜色的时候，查找当前位置左方和上方的颜色，看看是否同色。

就是一这部分相邻的隔开，可以得到两块陌生人集合，就能解决
 

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>arr;
vector<int>ok;
int m, n;
int reach;void check(int a, int b)
{int now = arr[a][b];int up[2] = { -1,0 };int right[2] = { 0,-1};for (int i = 0; i < 2; i++){if (a + up[i] < 0 || a + up[i] >= m || b + right[i] < 0 || b + right[i] >= n){continue;}if (arr[a + up[i]][b + right[i]] == now){if (ok[now] != -1){reach++;ok[now] = -1;}}}
}int main()
{int t;cin >> t;while (t--){cin >> m >> n;arr=vector<vector<int>>(m, vector<int>(n));ok= vector<int>(5000);int sum = 0;reach = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++){cin >> arr[i][j];if (ok[arr[i][j]]>0){check(i, j);}if (ok[arr[i][j]] == 0){ok[arr[i][j]]++;sum++;}//等于-1什么也不做}		if (reach > 0){cout << sum - reach + (reach - 1) * 2<<endl;}else{cout << sum-1 << endl;}}
}

超时，为什么呢？因为每次都会开一个5000大小的数组用来记住颜色，这样不行

试试键值对

#include <bits/stdc++.h>
using namespace std;vector<vector<int>> arr; // 存储表格数据
unordered_map<int, int> ok; // 使用 unordered_map 代替数组
int m, n; // 表格的行数和列数
int reach; // 记录满足某种条件的颜色数量// 检查函数：检查当前单元格的颜色是否与上方或左方的单元格颜色相同
void check(int a, int b) {int now = arr[a][b]; // 当前单元格的颜色int up[2] = { -1, 0 }; // 上方单元格的偏移量int right[2] = { 0, -1 }; // 左方单元格的偏移量// 检查上方和左方的单元格for (int i = 0; i < 2; i++) {// 检查边界条件，避免越界if (a + up[i] < 0 || a + up[i] >= m || b + right[i] < 0 || b + right[i] >= n) {continue; // 如果越界，跳过}// 如果上方或左方的单元格颜色与当前单元格相同if (arr[a + up[i]][b + right[i]] == now) {if (ok[now] != -1) { // 如果该颜色尚未被标记为冲突reach++; // 增加冲突计数ok[now] = -1; // 标记该颜色为冲突}}}
}int main() {int t; // 测试用例的数量cin >> t; // 读取测试用例数量while (t--) { // 处理每个测试用例cin >> m >> n; // 读取表格的行数和列数arr = vector<vector<int>>(m, vector<int>(n)); // 初始化表格ok.clear(); // 清空键值对int sum = 0; // 记录颜色的总数reach = 0; // 重置冲突计数// 读取表格数据并处理for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cin >> arr[i][j]; // 读取当前单元格的颜色if (ok[arr[i][j]] > 0) { // 如果该颜色已经出现过check(i, j); // 检查是否与相邻单元格冲突}if (ok[arr[i][j]] == 0) { // 如果该颜色第一次出现ok[arr[i][j]]++; // 标记该颜色存在sum++; // 增加颜色总数}// 如果 ok[arr[i][j]] == -1，说明该颜色已经标记为冲突，无需处理}}// 输出结果if (reach > 0) { // 如果存在冲突cout << sum - reach + (reach - 1) * 2 << endl; // 计算结果} else { // 如果没有冲突cout << sum - 1 << endl; // 直接输出颜色总数减 1}}return 0;
}

内存小炸裂，但是成功了