QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#130501 | #1943. Borders | karuna# | RE | 0ms | 0kb | C++17 | 2.7kb | 2023-07-24 12:55:38 | 2023-07-24 12:55:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int n, m; bool a[MAXN][MAXN];
int r[MAXN][MAXN];
void dfs(int x, int y, int z) {
if (r[x][y]) return;
r[x][y] = z;
for (int t = 0; t < 4; t++) {
int nx = x + dx[t];
int ny = y + dy[t];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[x][y] != a[nx][ny])
continue;
dfs(nx, ny, z);
}
}
vector<int> g[MAXN * MAXN];
bool dead[MAXN * MAXN];
bool vis[MAXN * MAXN];
int matched[MAXN * MAXN];
bool match(int v) {
if (vis[v]) false;
vis[v] = 1;
for (int x : g[v]) if (!dead[x]) {
if (matched[x] == -1 || match(matched[x])) {
matched[x] = v;
return true;
}
}
return false;
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s; cin >> s;
for (int j = 0; j < m; j++)
a[i][j] = s[j] - '0';
}
int rc = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (r[i][j]) continue;
dfs(i, j, ++rc);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m - 1; j++) {
if (r[i][j] == r[i][j + 1]) continue;
int u = r[i][j];
int v = r[i][j + 1];
if (u % 2 == 1) g[u].push_back(v);
else g[v].push_back(u);
}
}
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
if (r[i][j] == r[i + 1][j]) continue;
int u = r[i][j];
int v = r[i + 1][j];
if (u % 2 == 1) g[u].push_back(v);
else g[v].push_back(u);
}
}
int ans = 0;
for (int i = 0; i < n; i++) {
int u = r[i][0];
int v = r[i][m - 1];
if (!dead[u]) {
++ans; dead[u] = 1;
}
if (!dead[v]) {
++ans; dead[v] = 1;
}
}
for (int i = 0; i < m; i++) {
int u = r[0][i];
int v = r[n - 1][i];
if (!dead[u]) {
++ans; dead[u] = 1;
}
if (!dead[v]) {
++ans; dead[v] = 1;
}
}
for (int i = 1; i <= rc; i++) {
sort(g[i].begin(), g[i].end());
g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
}
for (int i = 1; i <= rc; i++) matched[i] = -1;
for (int i = 1; i <= rc; i++) {
if (dead[i]) continue;
for (int j = 1; j <= rc; j++) vis[j] = 0;
ans += match(i);
}
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
100 100 0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101 1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010 010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...