QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#364830 | #5071. Check Pattern is Good | sgweo8ys | WA | 48ms | 12284kb | C++14 | 4.2kb | 2024-03-24 16:53:36 | 2024-03-24 16:53:36 |
Judging History
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)