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

题意：
    现有一座n*n（0<=n<=4)的大城市，要你在没有障碍的地方放炮台，每个炮塔都会有向四面射击的机枪，子弹能够击穿本行本列所有除障碍物的其他物品。问你最多能放多少炮台。
解法：
    dfs+回溯 如果题目数据大一点还要用到二分匹配。我好喜欢的一道题目！

#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 = 4;
char mmap[N][N];
int n, mmax;
bool ok(int x, int y) {if(mmap[x][y] != '.') return false;for(int i = y-1; i >= 0; i--) {if(mmap[x][i] == 'X') break;if(mmap[x][i] == 'B') return false;}for(int i = x-1; i >= 0; i--) {if(mmap[i][y] == 'X') break;if(mmap[i][y] == 'B') return false;}return true;
}
void dfs(int pos, int num) {if(pos == n*n) {if(num > mmax) mmax = num;return;}int x = pos / n;int y = pos % n;if(ok(x, y)) {mmap[x][y] = 'B';dfs(pos+1, num+1);mmap[x][y] = '.';}dfs(pos+1, num);
}
int main() {while(cin >> n, n) {mmax = -1;for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {cin >> mmap[i][j];}}dfs(0, 0);cout << mmax << endl;}return 0;
}