1 条题解
-
0
#include <bits/stdc++.h> using namespace std; struct edge { int x, y, pre; } a[3000]; int alen, last[3000]; void ins(int x, int y) { ++alen; a[alen] = edge{ x, y, last[x] }; last[x] = alen; } int match[3000], chw[3000], tsp; bool dfs(int x) { for (int k = last[x]; k; k = a[k].pre) { int y = a[k].y; if (chw[y] != tsp) { chw[y] = tsp; if (match[y] == 0 || dfs(match[y]) == 1) { match[y] = x; return 1; } } } return 0; } char s[60][60]; int mapx[60][60], mapy[60][60]; int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%s", s[i] + 1); } int X = 0, Y = 0; for (int i = 1; i <= n; i++) { X++; for (int j = 1; j <= m; j++) { if (s[i][j] == '*') { if (s[i][j - 1] != '*') { X++; } mapx[i][j] = X; } } } for (int j = 1; j <= m; j++) { Y++; for (int i = 1; i <= n; i++) { if (s[i][j] == '*') { if (s[i - 1][j] != '*') { Y++; } mapy[i][j] = Y; } } } alen = 0; memset(last, 0, sizeof(last)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s[i][j] == '*') { ins(mapx[i][j], mapy[i][j]); } } } int ans = 0; memset(match, 0, sizeof(match)); memset(chw, 0, sizeof(chw)); for (int i = 1; i <= X; i++) { tsp = i; if (dfs(i)) { ans++; } } printf("%d\n", ans); return 0; }
- 1
信息
- ID
- 1466
- 时间
- 1000ms
- 内存
- 64MiB
- 难度
- 7
- 标签
- 递交数
- 189
- 已通过
- 44
- 上传者