ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#206832 | #3694. 染色 2 | Anthonyyan | 100 | 623ms | 2388kb | C++11 | 1.4kb | 2024-07-25 18:58:49 | 2024-07-25 20:13:33 |
answer
#include <bits/stdc++.h>
using namespace std;
int main(int, char const *[])
{
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
vector<vector<int>> G(n * m + 1);
vector<int> color(n * m + 1, -1);
vector<int> match(n * m + 1);
vector<int> vis(n * m + 1);
function<int(int, int)> index = [&](int x, int y)
{
return x * m + y + 1;
};
function<void(int, int)> addEdge = [&](int u, int v)
{
G[u].push_back(v);
G[v].push_back(u);
return;
};
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (a[i][j] == 'x')
continue;
int x = index(i, j);
if (i != 0 && a[i - 1][j] != 'x')
addEdge(x, index(i - 1, j));
if (j != 0 && a[i][j - 1] != 'x')
addEdge(x, index(i, j - 1));
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
int u = index(i, j);
sort(G[u].begin(), G[u].end());
}
function<bool(int, int)> dfs = [&](int u, int tag)
{
if (vis[u] == tag)
return false;
vis[u] = tag;
for (auto v : G[u])
{
if (!match[v] || dfs(match[v], tag))
{
match[v] = u;
return true;
}
}
return false;
};
int ans = 0;
for (int i = 1; i <= n * m; i++)
if (dfs(i, i))
ans++;
cout << (ans >> 1);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 1260kb
input:
4 5 ..... x.x.x x.x.x .....
output:
6
result:
ok "6"
Test #2:
score: 5
Accepted
time: 0ms
memory: 1264kb
input:
3 6 .x...x x.x.x. .....x
output:
3
result:
ok "3"
Test #3:
score: 5
Accepted
time: 0ms
memory: 1256kb
input:
1 20 ..xxx.xx...x....x..x
output:
5
result:
ok "5"
Test #4:
score: 5
Accepted
time: 0ms
memory: 1264kb
input:
5 4 .... x.x. ..x. .x.. ....
output:
8
result:
ok "8"
Test #5:
score: 5
Accepted
time: 8ms
memory: 1860kb
input:
10 1000 ....x..........x.x....x.x....x.......x.........................................x.....x.........
output:
4321
result:
ok "4321"
Test #6:
score: 5
Accepted
time: 5ms
memory: 1624kb
input:
10 1000 x..x..x................x..x...............x..x......x...x...x...x.x..x......xx.............x...
output:
3558
result:
ok "3558"
Test #7:
score: 5
Accepted
time: 2ms
memory: 1596kb
input:
10 1000 .xxx.x.x.xxx.xxx....xx.xxx.x....x..xx.........x.xxxxxx.xxxx....xx..xx...x....x.....xxxxx.xx....
output:
2754
result:
ok "2754"
Test #8:
score: 5
Accepted
time: 3ms
memory: 2388kb
input:
10000 1 . . . . . . . . . . . . . . . . . . . . . x . . . . . . . . . . . . . x . . . . . . . . x . ...
output:
4275
result:
ok "4275"
Test #9:
score: 5
Accepted
time: 211ms
memory: 1856kb
input:
100 100 .........x.................................x........x.......x............x.....................
output:
4567
result:
ok "4567"
Test #10:
score: 5
Accepted
time: 102ms
memory: 1860kb
input:
100 100 ......x..x...x.x........x...x..........x............x......x.....x..........x..x...............
output:
4078
result:
ok "4078"
Test #11:
score: 5
Accepted
time: 9ms
memory: 1628kb
input:
100 100 ......xxx.............x...x.xx.xx......x............x......x..x..x..........x.x...x...x...xx...
output:
3593
result:
ok "3593"
Test #12:
score: 5
Accepted
time: 4ms
memory: 1604kb
input:
100 100 .x..xxx.....x.x....x..x.....x..x...x.x..x.x...x.x.x...x..x.....x.x.....x....x.x..x.x.xx........
output:
3055
result:
ok "3055"
Test #13:
score: 5
Accepted
time: 48ms
memory: 1860kb
input:
100 100 ...............x......x...xx.x.x..xx.......x......x.......x............x..x.xx...x...x.x.x.x...
output:
3892
result:
ok "3892"
Test #14:
score: 5
Accepted
time: 46ms
memory: 1856kb
input:
101 99 .x.x...x.....x.........x.................x.....x.....x...x.x...x...x.....x.............x........
output:
3303
result:
ok "3303"
Test #15:
score: 5
Accepted
time: 9ms
memory: 1636kb
input:
101 99 ...x.............x.x...x.....x...x.x.............x.x.x.....x...x.x...........x.x.....x.....x....
output:
2801
result:
ok "2801"
Test #16:
score: 5
Accepted
time: 3ms
memory: 1604kb
input:
101 99 .....x.....x...x.x.x.........x.x.x.x.x...x.x...x.........x.x.x.x.x.......x.x.x.........x.x......
output:
2221
result:
ok "2221"
Test #17:
score: 5
Accepted
time: 3ms
memory: 1592kb
input:
101 99 ...x.x...x.x.x.x.x...x.x.x.x.x.x.x.x.....x.x.x...x.x.x.....x...x.....x.x...x...x.x.x...x.x.x....
output:
1634
result:
ok "1634"
Test #18:
score: 5
Accepted
time: 0ms
memory: 1592kb
input:
101 99 .x.x.x.x.x.x.x...x.x...x.x.x.x...x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x...x.x.x...x.x.x.x.x.x.x....
output:
1074
result:
ok "1074"
Test #19:
score: 5
Accepted
time: 0ms
memory: 1592kb
input:
101 99 .x.x...x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x...x.x.x.x.x.x...x.x.x...x.x.x....
output:
554
result:
ok "554"
Test #20:
score: 5
Accepted
time: 170ms
memory: 1860kb
input:
100 100 ...............x.................................x.......................................x.....
output:
4500
result:
ok "4500"