QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#130501#1943. Borderskaruna#RE 0ms0kbC++172.7kb2023-07-24 12:55:382023-07-24 12:55:55

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-24 12:55:55]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-07-24 12:55:38]
  • 提交

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;
}

详细

Test #1:

score: 0
Runtime Error

input:

100 100
0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

output:


result: