QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#271025 | #5071. Check Pattern is Good | liangbowen | RE | 298ms | 6320kb | C++14 | 3.8kb | 2023-12-01 20:36:15 | 2023-12-01 20:36:16 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
//#define EMPTY(arr) for (int i = 0; i <= 2 * n * m + 5; i++) arr[i] = 0
#define EMPTY(arr) memset(arr, 0, sizeof arr)
using namespace std;
const int N = 114514, inf = 0x3f3f3f3f, dict[9][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 0}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
struct Edge {int now, nxt, u, w;} e[1919810];
int head[N], _head[N], cur = 1;
void ad(int u, int v, int w) {e[++cur].now = v, e[cur].nxt = head[u], e[cur].w = w, head[u] = cur;}
void add(int u, int v, int w) {ad(u, v, w), ad(v, u, 0);}
int n, m, s, t; char a[105][105];
void chg(char &x) {x = (x == 'B' ? 'W' : x == 'W' ? 'B' : '?');}
bool black(char v) {return v != 'W';}
bool white(char v) {return v != 'B';}
int black(int x, int y) {return (x - 1) * m + y;}
int white(int x, int y) {return (x - 1) * m + y + n * m;}
bool all_black(int x, int y) {return black(a[x][y]) && black(a[x + 1][y]) && black(a[x][y + 1]) && black(a[x + 1][y + 1]);}
bool all_white(int x, int y) {return white(a[x][y]) && white(a[x + 1][y]) && white(a[x][y + 1]) && white(a[x + 1][y + 1]);}
pair <int, int> toxy(int u) {return (u % m == 0 ? (pair <int, int>){u / m, m} : (pair <int, int>){u / m + 1, u % m});}
namespace Flow {
int dis[N]; bool vis[N];
bool bfs()
{
queue <int> q; EMPTY(vis);
q.push(s), vis[s] = true, dis[s] = 0, _head[s] = head[s];
while (!q.empty())
{
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].now;
if (vis[v] || !e[i].w) continue;
vis[v] = true, dis[v] = dis[u] + 1, q.push(v), _head[v] = head[v];
if (v == t) return true;
}
}
return false;
}
int dfs(int u, int maxflow)
{
if (u == t) return maxflow;
int flow = 0;
for (int i = _head[u]; i && flow < maxflow; i = e[i].nxt)
{
_head[u] = i; int v = e[i].now;
if (dis[v] != dis[u] + 1 || !e[i].w) continue;
int ww = dfs(v, min(e[i].w, maxflow - flow));
if (!ww) dis[v] = -inf;
e[i].w -= ww, e[i ^ 1].w += ww, flow += ww;
}
return flow;
}
int dinic()
{
int ans = 0;
while (bfs()) ans += dfs(s, inf);
return ans;
}
}
bool flow[N];
void dfs(int u)
{
flow[u] = true;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].now;
if (!flow[v] && e[i].w) dfs(v);
}
}
void solve()
{
cin >> n >> m, s = 0, t = 2 * n * m + 1;
cur = 1; EMPTY(head); EMPTY(flow);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{cin >> a[i][j]; if ((i + j) & 1) chg(a[i][j]);}
int tot = 0;
for (int x = 1; x < n; x++)
for (int y = 1; y < m; y++)
{
//s 连 Black,t 连 White
if (all_black(x, y)) add(s, black(x, y), 1), tot++;
if (all_white(x, y)) add(white(x, y), t, 1), tot++;
for (int i = 0; i < 9; i++)
{
int dx = x + dict[i][0], dy = y + dict[i][1];
if (1 <= dx && dx < n && 1 <= dy && dy < m) add(black(x, y), white(dx, dy), inf);
}
}
cout << tot - Flow::dinic() << '\n'; //总数-最小割
dfs(s);
for (int i = 2; i <= cur; i += 2)
{
int u = e[i].u, v = e[i].now;
if ((flow[u] && flow[v]) || (!flow[u] && !flow[v])) //两者状态相同,说明中间的边没被割掉
{
if (u == s) {auto [x, y] = toxy(v); if (all_black(x, y)) a[x][y] = a[x + 1][y] = a[x][y + 1] = a[x + 1][y + 1] = 'B';}
if (v == t) {auto [x, y] = toxy(u - n * m); if (all_white(x, y)) a[x][y] = a[x + 1][y] = a[x][y + 1] = a[x + 1][y + 1] = 'W';}
}
}
for (int i = 1; i <= n; i++, cout << '\n')
for (int j = 1; j <= m; j++)
{
a[i][j] = (a[i][j] == '?' ? 'W' : a[i][j]);
if ((i + j) & 1) chg(a[i][j]);
cout << a[i][j];
}
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6056kb
input:
3 2 2 ?? ?? 3 3 BW? W?B ?BW 3 3 BW? W?W ?W?
output:
1 WB BW 1 BWW WWB WBW 4 BWB WBW BWB
result:
ok ok (3 test cases)
Test #2:
score: 0
Accepted
time: 161ms
memory: 6320kb
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 BWBBWWW WBWBWWB BWWWBWB BBWBBWB WWBWWWB BWBWWBW WWWWBBW BBWBBBW BWWWWWB 6 BWWBWWB WBBWWWB BWWBBBW BBBWBBB 0 B W W B B W W W B B 15 BWWW WBWW WWWB WBBW BWWB BWBW WBWB BWBW WBWW BWBW 8 WBW WWB WBW BWB WBW WWW WBW BWB 0 W B W B 1 WBWB WWBB 3 BW...
result:
ok ok (10000 test cases)
Test #3:
score: 0
Accepted
time: 155ms
memory: 6132kb
input:
10000 9 6 ?B?W?W WWBBWB ?WB?BW B?W?W? WW??W? B???BW ?W?WW? W?B?B? ?W?BB? 10 1 W ? ? ? ? ? ? ? B W 9 4 ???? ???? W??? ?W?B ??WW ?BW? WW?W ??W? ??W? 3 2 ?W ?B BB 2 7 ?W?BWWB ??W???W 9 9 ?BW?WWW?W BW?WBBWWW W?W????WW W??WW??WW W?BWB?B?W ??BB?WWWW W???WBW?W WWW???WWW B?WWWWWW? 8 10 W??BWWW??B ?BWBWBW?BW...
output:
21 WBWWBW WWBBWB WWBWBW BBWBWB WWBWWB BBWBBW BWBWWB WBBWBW BWWBBB 0 W B W B W B W B B W 15 WBWB BWBW WBWB BWBB WBWW BBWB WWBW WBWB BWWB 1 BW WB BB 4 BWBBWWB WBWWBBW 20 WBWBWWWBW BWBWBBWWW WBWBWWBWW WWBWWBWWW WBBWBWBBW BWBBBWWWW WBWBWBWBW WWWWBWWWW BBWWWWWWW 28 WWBBWWWBWB WBWBWBWWBW BWBWBWBWBW WBBWBW...
result:
ok ok (10000 test cases)
Test #4:
score: 0
Accepted
time: 160ms
memory: 6148kb
input:
10000 7 7 ?B??BBW ????BB? WBBB??B WW?B??? ?B??BBB BBWB??B B???BB? 10 6 W?WW?? W??W?? ?WWWW? ?WW?WW WW??W? W????? W?WW?? WW???W WWW??W ?W??W? 2 6 ?B??W? B???BB 1 8 ??BWB?W? 5 2 WB W? B? BB ?W 7 5 W???? ?WW?? ???W? WWWW? W?W?W ?W?B? W?WWB 8 5 B?WBW B??WW WWW?B WBBWB BW?WW B?W?B ??WWB BBW?B 10 4 WWWW ?...
output:
15 WBWBBBW BWBWBBW WBBBWWB WWWBWBW WBBWBBB BBWBWWB BWBWBBW 13 WBWWWB WWBWBW WWWWWB BWWWWW WWWBWB WWBWBW WBWWWB WWBWBW WWWBWW BWBWWW 4 WBWBWB BWBWBB 0 WBBWBBWB 1 WB WB BW BB WW 12 WBBWB BWWBW WBBWB WWWWB WBWBW BWBBW WBWWB 7 BBWBW BWBWW WWWBB WBBWB BWBWW BWWBB WBWWB BBWWB 9 WWWW BBWB WWBW WBWB BWWB BW...
result:
ok ok (10000 test cases)
Test #5:
score: 0
Accepted
time: 161ms
memory: 5904kb
input:
10000 1 1 ? 7 9 W?WB????B ?WB??B??W BBB?W?WB? WWW??WWW? WW?B??W?W ?BWW??WWW B?WW?W?WB 3 7 ??BBBB? BW?WW?? B??B?BW 1 6 ?B?WWB 7 1 W W W B ? W ? 8 8 WW??W?B? WWW????? BB??WWWW ?W???WBW BBW???WB BWBWBWW? ?W?WW??B BB?????W 10 8 WWW?W?BW WB?W?WBW WW?W?WBW WWWW?WW? WBWB?B?W BW?BW??B ??WWBWWB W?BW?BWW W?W?...
output:
0 W 18 WBWBWWBWB BWBWBBWBW BBBBWBWBW WWWWBWWWB WWBBWBWBW WBWWBWWWW BWWWWWWWB 5 WBBBBBW BWBWWWB BBWBWBW 0 WBWWWB 0 W W W B W W W 23 WWWBWBBW WWWWBWWB BBWBWWWW BWBWBWBW BBWBWBWB BWBWBWWW WWBWWBWB BBWBBWBW 19 WWWBWBBW WBBWBWBW WWWWWWBW WWWWBWWB WBWBWBBW BWBBWBWB WBWWBWWB WWBWBBWW WBWBWWWB WWWWBBBB 0 WB...
result:
ok ok (10000 test cases)
Test #6:
score: 0
Accepted
time: 161ms
memory: 4356kb
input:
10000 9 1 W B ? B W W ? W B 1 10 W??????BWB 5 8 ??W??WB? ?B?WWB?W ??????B? BB??BBBB WB??BBB? 6 2 ?B ?? WB ?B WW W? 1 10 WW??BW?BW? 4 3 BW? ??? B?B ??W 10 10 WW?BBW?BW? WW?BW????? ?WWBW?WB?W ???B?BBBBB ??BBBB?BBW ?WW??W?WBB W??BB?WBBB BBWBW?WBBW ?W????BWB? ??BW??WBWB 1 6 ??B??? 6 5 WBB?W ?WWWW WWWW? ...
output:
0 W B W B W W W W B 0 WBWBWBWBWB 10 BWWBBWBB WBBWWBWW BWWBWWBB BBBWBBBB WBWBBBBB 2 WB BW WB BB WW WW 0 WWWBBWWBWB 6 BWB WBW BWB WBW 26 WWWBBWWBWB WWBBWWBWBW BWWBWBWBWW WBWBBBBBBB BWBBBBWBBW BWWWBWBWBB WBWBBBWBBB BBWBWBWBBW BWBWBWBWBW WBBWWBWBWB 0 WBBBWB 4 WBBBW BWWWW WWWWB WWWBW WWBBW WBWWB 0 B B B ...
result:
ok ok (10000 test cases)
Test #7:
score: 0
Accepted
time: 298ms
memory: 4368kb
input:
10000 10 10 ?W?WW?W??W ?BWBW?BBWW ?BB?WWW?W? W?B?WWWWWW ?BWW?WWW?W BWWWWWWW?W WBBWW??B?? W??WW?W??W WWWW?WW?W? ?W?BWW?WW? 10 10 WB?WBBWWWB ?WWWW?WB?? ?B?BWW?BW? WBWBW??W?W B?WB?WBWWB WWBWBBWW?? ??WBBWBWBW WWB??WWBWB B?BWWWWBWW WW?WWWBWWB 10 10 ??W????WW? ?WW?W???W? ??W??WW?W? WW??WW?WW? ?W??WW?WW? ?...
output:
20 BWBWWBWWBW WBWBWWBBWW WBBWWWWBWB WWBBWWWWWW WBWWBWWWWW BWWWWWWWBW WBBWWWBBWB WWBWWBWWBW WWWWBWWBWB BWBBWWBWWW 24 WBWWBBWWWB BWWWWBWBBW WBWBWWBBWB WBWBWBWWBW BBWBWWBWWB WWBWBBWWBW WBWBBWBWBW WWBWBWWBWB BBBWWWWBWW WWBWWWBWWB 33 WBWWBWBWWB BWWBWBWBWW WBWBBWWBWB WWBWWWBWWW WWWBWWWWWB BWWWBWWWBW BWBBW...
result:
ok ok (10000 test cases)
Test #8:
score: 0
Accepted
time: 295ms
memory: 5872kb
input:
10000 10 10 ?BBBBWBBB? ??W???WB?? BB?W???BB? ?B???BBB?? W??BB?WBBB ?B?B???W?W ?????BB??? ?BW???B??? ???BBB??BB BWBBBBBBB? 10 10 BWW?WWB?BW ??B?WBBBWB B??BB??BWB BW?BWB???W ?WB?WWW?W? B??B??W?BB ?WBB?WBB?B BB??BBWBW? WB??WBB?BW ?B???B?W?? 10 10 ??WWWB??BB ?WW???WBWW ???W??W?WW ?W?B?W?W?? WWB?WBB??W B...
output:
34 WBBBBWBBBW BWWBWBWBWB BBBWBWBBBW BBWBWBBBWB WWBBBWWBBB WBWBWBBWBW BWBWBBBBWB WBWBWWBWBW WBWBBBWBBB BWBBBBBBBW 31 BWWBWWBWBW WBBWWBBBWB BWWBBWWBWB BWWBWBBWBW WWBWWWWBWB BBWBBBWWBB WWBBWWBBWB BBBWBBWBWB WBWBWBBWBW BBBWBBBWWB 33 WBWWWBBWBB BWWBBWWBWW WBBWWBWBWW BWWBBWBWBW WWBWWBBBWW BBWBWBWWWW WWBWB...
result:
ok ok (10000 test cases)
Test #9:
score: 0
Accepted
time: 134ms
memory: 5856kb
input:
10000 1 100 WWW?BWB?BB?BBW?BWBB?W??B?B?BWWBWB?WWB??BBBBB??BBBBB?BBBWBWWW?B?BBBWW??BBBW???B???W??W??BW?B?B?W??WB? 1 100 ?WBW?WB?BBBB?BWBWB???WWB?BBB?BBW?B?B??W?B??BBW??WBBW???WW?BBBB?WWB?WBB???WBBB?BBW?W??BW?B??BBBBBBBWB 1 100 W?????BBB?BB?BB?????BWWWB?B???BB??????B??BWW???B??B?B???????BBB??B?BBB???B...
output:
0 WWWBBWBBBBWBBWWBWBBBWBWBWBWBWWBWBBWWBBWBBBBBWBBBBBBBBBBWBWWWWBWBBBWWWBBBBWWBWBWBWWWBWBWBWBBBBBWBWWBB 0 WWBWWWBBBBBBWBWBWBWBWWWBWBBBWBBWWBWBWBWBBBWBBWWBWBBWWBWWWBBBBBWWWBWWBBWBWWBBBBBBWBWBWBWBBBWBBBBBBBWB 0 WBWBWBBBBBBBWBBBWBWBBWWWBBBBWBBBWBWBWBBBWBWWWBWBWBBBBBWBWBWBBBBBWBWBBBWBWBBBWWWBWBWWWBWBWBWB...
result:
ok ok (10000 test cases)
Test #10:
score: 0
Accepted
time: 152ms
memory: 4340kb
input:
10000 100 1 W B B ? B B B ? B B B B W B B B ? ? B ? B B ? W B W ? B ? B W W ? W ? B ? B B ? W W B ? B B ? ? W W B B ? B B ? B ? ? ? W B W B ? B W ? ? B B B B ? B ? W B B W B ? W B B ? B B ? B ? W ? B ? B B ? B W 100 1 ? W ? W ? W W W W W B W ? ? B B ? W ? B W W W W ? ? ? ? W W B W W W W W ? W W W ? ...
output:
0 W B B B B B B B B B B B W B B B W B B B B B W W B W W B W B W W W W W B W B B B W W B B B B W B W W B B W B B B B B W B W B W B W B W B W B B B B B B B W B B W B B W B B B B B W B W W W B W B B B B W 0 W W W W W W W W W W B W W B B B W W W B W W W W W B W B W W B W W W W W W W W W W W B W W B W B ...
result:
ok ok (10000 test cases)
Test #11:
score: 0
Accepted
time: 298ms
memory: 5824kb
input:
1000 100 10 WWWB?WWW?W W????????W WB?W??WW?W WBB?WWW??B ?WWWW?WW?W ?WWWW?W?WB ?B??W?W??? WW?W?BWWW? WW?B?W?W?W ????WW??W? BWB??WWWW? W??W??WW?? W?WBB??WWW ?WWBBWW?WW ?WBWW?B??? ???WWW???W ??WW?WWW?? ????W?BW?W ???W?W?W?W ?WW?WW?WB? BW??WW?WW? WB?WWWWW?W ??BWW??W?W W??B?WWWW? WWW?W??WWW BBBW??W?W? ??...
output:
335 WWWBWWWWBW WWBWBWBBWW WBWWWBWWBW WBBWWWWBWB BWWWWBWWBW BWWWWWWBWB WBWBWBWWBW WWBWBBWWWB WWWBWWBWBW WBWBWWWBWB BWBWBWWWWB WWBWWBWWBW WBWBBWBWWW BWWBBWWBWW BWBWWBBWWB WBWWWWWBBW BWWWBWWWWB WBWBWBBWBW BWBWBWWWWW BWWBWWBWBW BWBWWWWWWB WBWWWWWWBW BWBWWBWWBW WBWBBWWWWB WWWBWBBWWW BBBWBWWBWB WBWBWWBWBW...
result:
ok ok (1000 test cases)
Test #12:
score: 0
Accepted
time: 282ms
memory: 4568kb
input:
1000 10 100 BBWB??W??B?BWB?BBB??WWWW?B???WBB??WW???WWBW?B??W??BW?BWBBBW?BWBW?WBW?B?WWB??B?B?BBWWWBBBBW?BB???B?WB ??????WWWBWBBB??W??WW??BWBW??W??????WWWB?B??B?????W?B?????W??BBBBWBW??BWWWB???WBWB?BB?WW?B????W?WWB? WB?BBBW?B??BB?WWW?B??WBB??W?BBW??BB??BB???BB??B??WB??W?B?B?WWWWW?BB??W?W?WBB??B?WWBBB?...
output:
330 BBWBWBWBWBWBWBWBBBWBWWWWBBBWBWBBWBWWBBBWWBWBBWBWBWBWWBWBBBWWBWBWWWBWWBWWWBWBBWBWBBWWWBBBBWWBBWBWBBWB BWBWBWWWWBWBBBBWWWBWWBWBWBWBWWBWBWBBWWWBWBBWBBWBWBWBBWBWBWWBWBBBBWBWBWBWWWBWWBWBWBWBBWWWWBBWBBWBWWBW WBWBBBWBBWBBBBWWWBBWBWBBBWWWBBWBWBBBWBBWBWBBWWBWBWBWBWWBWBBWWWWWWBBBWWWWWWBBBWBBWWBBBBBWWBWBWW...
result:
ok ok (1000 test cases)
Test #13:
score: -100
Runtime Error
input:
100 100 100 ?WW?WW??WWW??BBW??WW??W???W?W?W?????W?W?BWBW??WBW????W??BB??BW?W??W????WBW?????WWB??BWW????W??W??WW? B?????WW???B?BWWWB?WWW?WB?BB??????W??W?BWWW?BB??WWBWB?WWW????WW?W??BB?BBWB?W????W???BWWW??BBWWW???BW W?BW??????WBB?B????W?BBW????BBW????W?W?????B?B??WW??????WWWWW?W??WW?WBW??W??W????BWWB?...
output:
4352 WWWBWWBBWWWWBBBWBWWWWBWBWBWBWBWWBWBWWBWWBWBWWBWBWBWBWWBBBBWBBWBWBWWBWBWWBWWBWBWWWBWBBWWBWBWWBBWWBWWB