QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#364830#5071. Check Pattern is Goodsgweo8ysWA 48ms12284kbC++144.2kb2024-03-24 16:53:362024-03-24 16:53:36

Judging History

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

  • [2024-03-24 16:53:36]
  • 评测
  • 测评结果:WA
  • 用时:48ms
  • 内存:12284kb
  • [2024-03-24 16:53:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int K = 110;
const int N = 1000010, M = 2000010;
const int inf = 0x3f3f3f3f;

int n, m, T;
char mp[K][K], mp1[K][K];

int s, t, cnt = 1, head[N], nxt[M], to[M], d[N], now[N];
LL flow, maxflow, w[M];

inline void addedge(int u, int v, int k)
{
    to[++cnt] = v; w[cnt] = k;
    nxt[cnt] = head[u], head[u] = cnt;
}

inline int get(int x, int y, int c)
{
    return (x - 1) * m + y + c * (n * m);
}

void link(int x, int y)
{
    addedge(x, y, inf);
    addedge(y, x, 0);
}

bool bfs()
{
    for(int i = 1; i <= t; i++) d[i] = 0;
    d[s] = 1;
    queue <int> q;
    q.push(s);
    while(!q.empty()){
        int u = q.front(); q.pop();
        now[u] = head[u];
        for(int i = head[u]; i; i = nxt[i]){
            int v = to[i];
            if(!d[v] && w[i]){
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
    return d[t];
}

LL dinic(int u, LL limit)
{
    if(u == t || limit == 0) return limit;
    LL rest = limit;
    for(int i = now[u]; i; i = nxt[i]){
        now[u] = i;
        int v = to[i];
        if(w[i] && d[v] == d[u] + 1){
            LL k = dinic(v, min(rest, w[i]));
            if(!k) d[v] = 0;
            w[i] -= k, w[i ^ 1] += k, rest -= k;
        }
    }
    return limit - rest;
}

void solve()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if((i + j) & 1){
                if(mp[i][j] == 'W') mp[i][j] = 'B';
                else if(mp[i][j] == 'B') mp[i][j] = 'W';
            }
        }
    }

    s = 2 * n * m + 1, t = 2 * n * m + 2;
    for(int i = 1; i < n; i++){
        for(int j = 1; j < m; j++){
            if(mp[i][j] != 'B' && mp[i + 1][j] != 'B' && mp[i][j + 1] != 'B' && mp[i + 1][j + 1] != 'B'){
                addedge(s, get(i, j, 0), 1);
                addedge(get(i, j, 0), s, 0);
            }
            if(mp[i][j] != 'W' && mp[i + 1][j] != 'W' && mp[i][j + 1] != 'W' && mp[i + 1][j + 1] != 'W'){
                addedge(t, get(i, j, 1), 0);
                addedge(get(i, j, 1), t, 1);
            }
            link(get(i, j, 0), get(i, j, 1));
            if(i < n - 1){
                link(get(i, j, 0), get(i + 1, j, 1));
                if(j < m - 1) link(get(i, j, 0), get(i + 1, j + 1, 1));
                if(j > 1) link(get(i, j, 0), get(i + 1, j - 1, 1));
            }
            if(i > 1){
                link(get(i, j, 0), get(i - 1, j, 1));
                if(j < m - 1) link(get(i, j, 0), get(i - 1, j + 1, 1));
                if(j > 1) link(get(i, j, 0), get(i - 1, j - 1, 1));
            }
            if(j < m - 1) link(get(i, j, 0), get(i, j + 1, 1));
            if(j > 1) link(get(i, j, 0), get(i, j - 1, 1));
        }
    }

    while(bfs())
        while(flow = dinic(s, inf)) maxflow += flow;


    int ans = 0;
    for(int i = head[s]; i; i = nxt[i]){
        int v = to[i];
        int x = (v - 1) / m + 1, y = (v - 1) % m + 1;

        if(w[i] != 0){
            ans++;
            mp[x][y] = 'W', mp[x + 1][y] = 'W', mp[x][y + 1] = 'W', mp[x + 1][y + 1] = 'W';
        }
        
    }

    for(int i = head[t]; i; i = nxt[i]){
        int v = to[i] - n * m;
        int x = (v - 1) / m + 1, y = (v - 1) % m + 1;

        ans++;
        mp[x][y] = 'B', mp[x + 1][y] = 'B', mp[x][y + 1] = 'B', mp[x + 1][y + 1] = 'B';
    }
    printf("%d\n", ans);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(mp[i][j] == '?') mp[i][j] = 'W';
            if((i + j) & 1){
                if(mp[i][j] == 'W') mp[i][j] = 'B';
                else mp[i][j] = 'W';
            }
            putchar(mp[i][j]);
        }
        putchar('\n');
    }


    for(int i = 1; i <= cnt; i++) to[i] = w[i] = nxt[i] = 0;
    for(int i = 1; i <= t; i++) head[i] = d[i] = now[i] = 0;
    s = t = flow = maxflow = 0;
    cnt = 1;
}

int main()
{
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}
/*
3
10 7
WBBBW??
???BWWW
???BWWB
??WWBW?
BBWBBWB
WWB?WW?
BWBW???
WWWWBBW
BBWBB?W
B?W?W?B
4 7
??WBWWB
?BBWWWB
?W?BBB?
BBBWBBB
*/

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 12012kb

input:

3
2 2
??
??
3 3
BW?
W?B
?BW
3 3
BW?
W?W
?W?

output:

1
BW
WB
1
BWW
WBB
WBW
4
BWB
WBW
BWB

result:

ok ok (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 48ms
memory: 12284kb

input:

10000
9 2
BB
BW
WW
WW
?W
?B
B?
W?
BB
6 2
??
?B
B?
BW
WW
??
10 7
WBBBW??
???BWWW
???BWWB
??WWBW?
BBWBBWB
WWB?WW?
BWBW???
WWWWBBW
BBWBB?W
B?W?W?B
4 7
??WBWWB
?BBWWWB
?W?BBB?
BBBWBBB
10 1
B
W
?
B
B
W
W
W
B
?
10 4
??WW
W?W?
WWW?
???W
?W??
?W?W
W?W?
?W?W
???W
???W
8 3
WBW
W??
???
???
W?W
W?W
???
?W?
4 1
...

output:

3
BB
BW
WW
WW
BW
WB
BW
WB
BB
2
BW
WB
BW
BW
WW
BW
9
WBBBWBW
WBWBWWW
BWBBWWB
WBWWBWB
BBWBBWB
WWBBWWB
BWBWBWB
WWWWBBW
BBWBBWW
BWWWWBB
6
BWWBWWB
WBBWWWB
BWWBBBW
BBBWBBB
0
B
W
W
B
B
W
W
W
B
B
15
BWWW
WBWW
WWWB
WBWW
BWBB
BWBW
WBWB
BWBW
BWBW
WBWW
8
WBW
WBW
BWB
WBW
WBW
WBW
BWB
BWB
0
W
B
W
B
1
WBWB
WWBB
3
BW...

result:

wrong answer There are 11 check pattern in you output, but you answered 15 (test case 6)