Fire Net

In a square of 4 × 4 at most, it is similar to the chessboard problem, but some points become "walls". If there are walls in the same row or column, the points on both sides of the wall will not be affected.

Idea: for ordinary chessboard problems, you only need to make a map of each row or column as a point, but this is obviously not possible because of the existence of walls,

It can be thought that for ordinary chessboard problems, when there is no wall, each row and column is exactly one point, one column and one point, so the continuous "." is regarded as a point. So for this problem, for each row or column, the continuous "." is still regarded as a point until the wall is met.

In this way, we can use the reconstructed points to build the map and run another Hungary.

#include<bits/stdc++.h>
#define exp 1e-8
#define mian main
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ll long long
#define pb push_back
#define PI  acos(-1.0)
#define inf 0x3f3f3f3f
#define w(x) while(x--)
#define int_max 2147483647
#define lowbit(x) (x)&(-x)
#define gcd(a,b) __gcd(a,b)
#define pq(x)  priority_queue<x>
#define ull unsigned long long
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define pl(a,n) next_permutation(a,a+n)
#define ios ios::sync_with_stdio(false)
#define met(a,x) memset((a),(x),sizeof((a)))
using namespace std;
char a[20][20];
int n,e[20][20],cnt_row,cnt_col,row[20][20],col[20][20];
bool used[20];
int cy[20],cx[20];
bool line(int x)
{
    for(int i=1;i<=cnt_col;i++){
        if(!used[i]&&e[x][i]){
            used[i]=1;
            if(cy[i]==-1||line(cy[i])){
                cy[i]=x;
                return true;
            }
        }
    }
    return false;
}
int maxmatch()
{
    int ans=0;
    met(cy,-1);
    met(cx,-1);
    for(int i=1;i<=cnt_row;i++){
        met(used,0);
        ans+=line(i);
    }
    return ans;
}
int main()
{
    while(~scanf("%d",&n)&&n){
            met(a,0);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
               cin>>a[i][j];
               met(e,0);
                cnt_row=0;
                cnt_col=0;
                met(row,0);
                met(col,0);
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(a[i][j]=='.'&&row[i][j]==0){ //Process each line
                cnt_row++;
                for(int k=j;k<=n&&a[i][k]=='.';k++)  //Assign a continuous point to a value
                    row[i][k]=cnt_row;
            }
            if(a[i][j]=='.'&&col[i][j]==0){//Process each column
                cnt_col++;
                for(int k=i;k<=n&&a[k][j]=='.';k++)
                    col[k][j]=cnt_col;
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]=='.')  //When the point is "." connect the two points of row and column into a new edge
            e[row[i][j]][col[i][j]]=1;
        int ans=maxmatch(); //Two score matching
        printf("%d\n",ans);
    }
}