HDU 1045 Fire Net(二分图匹配或爆搜)

#include <bits/stdc++.h>
#define maxn 15
using namespace std;
string str[maxn];
int n,ans;

bool Check(int x,int y){    // 判断这个点之前的行和列是否放置过
  for(int i=x-1;i>=0;i--){
    if(str[i][y] == 'X'){
      break;
    }
    if(str[i][y] == 'O') return false;
  }
  for(int i=y-1;i>=0;i--){
    if(str[x][i] == 'X'){
      break;
    }
    if(str[x][i] == 'O'){
      return false;
    }
  }
  return true;
}

void dfs(int cnt, int xx){  // cnt用来枚举地图 xx表示放置的数量
  if(cnt == n * n){
    ans = max(ans, xx);
    return ;
  }
  int x = cnt / n;    // 行
  int y = cnt % n;    // 列
  if(str[x][y] == '.' && Check(x, y)){
    str[x][y] = 'O';
    dfs(cnt + 1, xx + 1);
    str[x][y] = '.';
  }
  dfs(cnt + 1, xx);
}

int main()
{
  while(~scanf("%d",&n)){
    if(n == 0) break;
    for(int i=0;i<n;i++){
      cin>>str[i];
    }
    ans = 0;
    dfs(0, 0);
    printf("%d\n",ans);
  }
  return 0;
}

#include <bits/stdc++.h>
#define maxn 15
using namespace std;
string str[maxn];
int xx[maxn][maxn], yy[maxn][maxn];
bool edge[maxn][maxn], vis[maxn];
int pre[maxn];
int n, row, col;

bool dfs(int x){       // 匈牙利算法
  for(int i=1;i<=col;i++){
    if(edge[x][i] && vis[i] == false){
      vis[i] = true;
      if(pre[i] == -1 || dfs(pre[i])){
        pre[i] = x;
        return true;
      }
    }
  }
  return false;
}

int Fun(){
  int sum = 0;
  memset(pre,-1,sizeof(pre));
  for(int i=1;i<=row;i++){      // 从1开始
    memset(vis,false,sizeof(vis));
    if(dfs(i))
      sum ++;
  }
  return sum;
}

int main()
{
  while(~scanf("%d",&n)){
    if(n == 0) break;
    for(int i=0;i<n;i++) cin>>str[i];
    row = col = 0;
    for(int i=0;i<n;i++){           // 将块压缩成点
      for(int j=0;j<n;j++){
        if(str[i][j] == '.'){
          if(j == 0 || str[i][j-1] == 'X') row ++;
          xx[i][j] = row;
        }
        if(str[j][i] == '.'){
          if(j == 0 || str[j-1][i] == 'X') col ++;
          yy[j][i] = col;
        }
      }
    }
    memset(edge,false,sizeof(edge));
    for(int i=0;i<n;i++){             // 枚举点  进行连边
      for(int j=0;j<n;j++){
        if(str[i][j] == '.'){
          edge[ xx[i][j] ][ yy[i][j] ] = true;
        }
      }
    }
    int ans = Fun();
    printf("%d\n",ans);
  }
  return 0;
}