ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#206818 | #3694. 染色 2 | marcuse | 100 | 801ms | 2992kb | C++ | 1.6kb | 2024-07-25 18:34:20 | 2024-07-25 20:11:07 |
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 20000 + 10;
int read(){
char ch; int sum = 0,flag = 1;
ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') flag = -flag; ch = getchar();}
while(ch >= '0' && ch <= '9'){sum = sum * 10 + ch - '0'; ch = getchar();}
return flag * sum;
}
vector <int> G[N];
int n,m,num,ans;
bool vis[N];
int match[N];
void Add(int x,int y){
// cout << x << " " << y << endl;
G[x].push_back(y);
return ;
}
int dfs(int x){
for(int i = 0; i < G[x].size(); i++){
int y = G[x][i];
if(vis[y]) continue;
vis[y] = true;
if(!match[y] || dfs(match[y])){
match[y] = x;
match[x] = y;
return true;
}
}
return false;
}
signed main(){
n = read(); m = read();
int Map[n + 5][m + 5],tag[n + 5][m + 5];
memset(tag,0,sizeof(tag));
memset(Map,0,sizeof(Map));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
char ch;
cin >> ch;
if(ch == '.') Map[i][j] = 1,tag[i][j] = ++num;
else Map[i][j] = 0;
}
}
// for(int i = 1; i <= n; i++){
// for(int j = 1; j <= m; j++){
// cout << tag[i][j] << " ";
// }
// cout << endl;
// }
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(!Map[i][j]) continue;
if(Map[i - 1][j]) Add(tag[i][j],tag[i - 1][j]);
if(Map[i][j - 1]) Add(tag[i][j],tag[i][j - 1]);
if(Map[i + 1][j]) Add(tag[i][j],tag[i + 1][j]);
if(Map[i][j + 1]) Add(tag[i][j],tag[i][j + 1]);
}
}
for(int i = 1; i <= num; i++){
memset(vis,0,sizeof(vis));
if(!match[i])
if(dfs(i)) ans++;
}
printf("%d\n",ans);
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 1712kb
input:
4 5 ..... x.x.x x.x.x .....
output:
6
result:
ok "6"
Test #2:
score: 5
Accepted
time: 0ms
memory: 1720kb
input:
3 6 .x...x x.x.x. .....x
output:
3
result:
ok "3"
Test #3:
score: 5
Accepted
time: 0ms
memory: 1716kb
input:
1 20 ..xxx.xx...x....x..x
output:
5
result:
ok "5"
Test #4:
score: 5
Accepted
time: 0ms
memory: 1712kb
input:
5 4 .... x.x. ..x. .x.. ....
output:
8
result:
ok "8"
Test #5:
score: 5
Accepted
time: 31ms
memory: 2444kb
input:
10 1000 ....x..........x.x....x.x....x.......x.........................................x.....x.........
output:
4321
result:
ok "4321"
Test #6:
score: 5
Accepted
time: 15ms
memory: 2308kb
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: 10ms
memory: 2224kb
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: 9ms
memory: 2992kb
input:
10000 1 . . . . . . . . . . . . . . . . . . . . . x . . . . . . . . . . . . . x . . . . . . . . x . ...
output:
4275
result:
ok "4275"
Test #9:
score: 5
Accepted
time: 214ms
memory: 2424kb
input:
100 100 .........x.................................x........x.......x............x.....................
output:
4567
result:
ok "4567"
Test #10:
score: 5
Accepted
time: 105ms
memory: 2320kb
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: 18ms
memory: 2260kb
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: 13ms
memory: 2200kb
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: 56ms
memory: 2300kb
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: 75ms
memory: 2300kb
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: 23ms
memory: 2260kb
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: 14ms
memory: 2204kb
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: 10ms
memory: 2144kb
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: 7ms
memory: 2076kb
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: 6ms
memory: 2004kb
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: 195ms
memory: 2392kb
input:
100 100 ...............x.................................x.......................................x.....
output:
4500
result:
ok "4500"