很《简单》

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 55;
char grid[MAXN][MAXN];
int rowId[MAXN][MAXN], colId[MAXN][MAXN];
int rowCnt = 0, colCnt = 0;
vector<int> adj[MAXN * MAXN];
int match[MAXN * MAXN];
bool visited[MAXN * MAXN];

bool dfs(int u) {
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
if (match[v] == -1 || dfs(match[v])) {
match[v] = u;
return true;
}
}
}
return false;
}

int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> grid[i][j];
}
}

// Assign row IDs
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == '*' || grid[i][j] == 'x') {
if (j == 0 || grid[i][j - 1] == '#') {
rowId[i][j] = ++rowCnt;
} else {
rowId[i][j] = rowId[i][j - 1];
}
}
}
}

// Assign column IDs
for (int j = 0; j < m; ++j) {
for (int i = 0; i < n; ++i) {
if (grid[i][j] == '*' || grid[i][j] == 'x') {
if (i == 0 || grid[i - 1][j] == '#') {
colId[i][j] = ++colCnt;
} else {
colId[i][j] = colId[i - 1][j];
}
}
}
}

// Build bipartite graph
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (grid[i][j] == '*') {
int u = rowId[i][j];
int v = colId[i][j];
adj[u].push_back(v);
}
}
}

// Hungarian algorithm
memset(match, -1, sizeof(match));
int ans = 0;
for (int u = 1; u <= rowCnt; u) {
memset(visited, false, sizeof(visited));
if (dfs(u)) {
ans;
}
}

cout << ans << endl;
return 0;
}