记录编号	271814	评测结果	AAAAAAAAAA
题目名称	[ZOJ 1654]放置机器人	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2016-06-16 11:39:06	内存使用	10.58 MiB

#include<bits/stdc++.h> 
using namespace std;

int R, C;
int cross[1550][1550]/*横着的块*/, upright[1550][1550]/*竖着的块*/, crosscnt, uprightcnt;
char field[1550][1550]; 
int cx[1550], cy[1550] = {0}, visited[1550], ans;
int head[1550], tot;
struct Edge{
	int to, next;
	Edge()
	{
		to = next = 0;
	}
}edges[26000];

void AddEdge(int from, int to)
{
	edges[++tot].to = to;
	edges[tot].next = head[from];
	head[from] = tot;
}

int Hungary(int x)
{
	for(int i = head[x]; i; i = edges[i].next){
		int to = edges[i].to;
		if(!visited[to]){
			visited[to] = 1;
			if(!cx[to] || Hungary(cx[to])){
				cx[to] = x;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	freopen("placetherobots.in", "r", stdin);freopen("placetherobots.out", "w", stdout);
	scanf("%d%d", &R, &C);
	for(int i = 1; i <= R; i++){
			scanf("%s", field[i]+1);
	}	
	
	for(int i = 1; i <= R; i++){
		for(int j = 1; j <= C; j++){
			if((field[i][j] == '*' || field[i][j] == 'o') && !cross[i][j]){
				cross[i][j] = ++crosscnt;
				for(int k = j; ; k++){
					if(field[i][k] == '*' || field[i][k] == 'o')
						cross[i][k] = crosscnt;
					else break;	
				}
			}
		}
	}
	for(int j = 1; j <= C; j++){
		for(int i = 1; i <= R; i++){
			if((field[i][j] == '*' || field[i][j] == 'o') && !upright[i][j]){
				upright[i][j] = ++uprightcnt;
				for(int k = i; ; k++){
					if(field[k][j] == '*' || field[k][j] == 'o')
						upright[k][j] = uprightcnt;
					else break;	
				}
			}
		}
	}
//	for(int i = 1; i <= R; i++){
//		for(int j = 1; j <= C; j++)
//			printf("%d ", cross[i][j]);
//		puts("");
//	}	
	for(int i = 1; i <= R; i++){
		for(int j = 1; j <= C; j++){
			if(field[i][j] == 'o')
				AddEdge(cross[i][j], upright[i][j]);
		}
	}

	for(int i = 1; i <= crosscnt + uprightcnt; i++){
			memset(visited, 0, sizeof(visited));
			ans += Hungary(i);
	}	
			
	printf("%d", ans);		
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
4 4
*.*.
.***
***.
..*.
*/