0pts 每个点都是4 但是我考虑软石头了
查看原帖
0pts 每个点都是4 但是我考虑软石头了
97287
小胖同学楼主2022/10/11 23:00

看到有人说不考虑软石头会出错这样的错

但是我考虑了啊

#include<bits/stdc++.h>
using namespace std;
#define xztx main
int n , m , ans;
int mp_l[52][52] , mp_h[52][52] , cnt; // # -> -1 ; x -> -2 ; * -> cnt
struct Node{
	int next , to;
}e[5000];
int h[5000] , Size;
void add(int a , int b){
	e[++ Size].to = b , e[Size].next = h[a] , h[a] = Size;
}
int vis[5000] , col[5000];
bool Find(int x){
//	cout <<"--"<< x <<"\n";
	for(int i = h[x];i;i = e[i].next){
		int y = e[i].to;
		if(!vis[y]){
			vis[y] = 1;
			if(!col[y] || Find(col[y])){
				col[x] = y;
				return 1;
			}
		}
	}
	return 0;
}
int xztx(){
	ios :: sync_with_stdio(0);
	cin . tie(0);
	char c;
	cin >> n >> m;
	for(int i = 1;i <= n;++ i) mp_h[i][m + 1] = -1;
	for(int i = 1;i <= m;++ i) mp_l[n + 1][i] = -1; //  预处理右(下)边一排硬石头
	
	for(int i = 1 , f = 1;i <= n;++ i)
		for(int j = 1;j <= m + 1;++ j){
		if(j <= m) cin >> c;
		if(c == '#') mp_l[i][j] = mp_h[i][j] = -1;
		if(c == 'x') mp_l[i][j] = mp_h[i][j] = -2;
		if(mp_h[i][j] == -1){// 是硬石头 
			if(!f) continue; // 且 不是连着的硬石头
			f = 0 , ++ cnt;
			continue;
		}	
		if(!mp_h[i][j]) mp_h[i][j] = cnt , f = 1;
	}
	///////////////////////////////////////////////////// 行初始化
	for(int i = 1 , f = 1;i <= m;++ i)
		for(int j = 1;j <= n + 1;++ j){
		if(mp_l[j][i] == -1){// 是硬石头 
			if(!f) continue; // 且 不是连着的硬石头
			f = 0 , ++ cnt;
			continue;
		}	
		if(!mp_l[j][i]) mp_l[j][i] = cnt , f = 1;
	}
	////////////////////////////////////////////////////// 列初始化
//	for(int i = 1;i <= n;i ++){
//		for(int j = 1;j <= m;j ++){
//			cout << mp_h[i][j] <<" ";
//		}
//		cout << endl;
//	}for(int i = 1;i <= n;i ++){
//		for(int j = 1;j <= m;j ++){
//			cout << mp_l[i][j] <<" ";
//		}
//		cout << endl;
//	}
	for(int i = 1;i <= n;++ i){
		for(int j = 1;j <= m;++ j){
			if(mp_l[i][j] < 0 || mp_h[i][j] < 0){continue;}
//			cout<< mp_h[i][j] <<" " << mp_l[i][j] << endl;
			add(mp_h[i][j] , mp_l[i][j]);
			add(mp_l[i][j] , mp_h[i][j]);
		}
	}
//	cout << 1;
	//////////////////////////////////////////// 加边
	for(int i = 1;i <= cnt;++ i){
		memset(vis , 0 , sizeof vis);	
		ans += Find(i);
//		cout << ans;
	}		
		
	cout << ans;
	return 0;
}
/*
	
4 4
#*x*
*#**
**#*
xxx#
*/
2022/10/11 23:00
加载中...