[面试备] 暴搜 or 二分图的经典升级 ： hdu 1045 Fire Net 示例 [ 二分图 ]

#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <map>
#include <set>
#include <iterator>
#include <algorithm>
#include <functional>
#include <utility>
#include <sstream>
#include <climits>
#include <cassert>
#define BUG puts("here!!!");using namespace std;
const int N = 5;
const int M = 30;
char str[N][N];
int p[N][N];
int rp[N][N];
int mmap[M][M];
int pre[M];
bool vis[M];
int n;
int x_id, y_id;
bool dfs(int u) {for(int i = 1; i <= y_id; i++) {if(mmap[u][i] && !vis[i]) {vis[i] = true;if(pre[i] == 0 || dfs(pre[i])) {pre[i] = u;return true;}}}return false;
}
int maxMatch() {memset(pre, 0, sizeof(pre));int num = 0;for(int i = 1; i <= x_id; i++) {memset(vis, 0, sizeof(vis));if(dfs(i)) num++;}return num;
}
int main() {while(cin >> n, n) {for(int i = 0; i < n; i++) {scanf("%s", str[i]);}memset(p, 0, sizeof(p));memset(rp, 0, sizeof(rp));x_id = 0, y_id = 0;for(int i = 0; i < n; i++) {int k = 0;while(k < n) {if(str[i][k] == '.') {++x_id;while(k < n && str[i][k] != 'X') {p[i][k] = x_id;k++;}}else k++;}}for(int i = 0; i < n; i++) {int k = 0;while(k < n) {if(str[k][i] == '.') {++y_id;while(k < n && str[k][i] != 'X') {rp[k][i] = y_id;k++;}}else k++;}}memset(mmap, 0, sizeof(mmap));for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {if(str[i][j] == '.') {mmap[p[i][j]][rp[i][j]] = 1;}}}printf("%d\n", maxMatch());}return 0;
}