UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#206818#3694. 染色 2marcuse100801ms2992kbC++1.6kb2024-07-25 18:34:202024-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"