Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.
A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.
Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.
The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.
The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.
Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.
Input
The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a '.' indicating an open space and an uppercase 'X' indicating a wall. There are no spaces in the input file.
Output
For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration.
Sample Input
4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0 Sample Output
5
1
5
2
4 题目大意:(抽象)你需要在一个棋盘上放一些棋子,棋子对每一行每一列都可以直线攻击,有一些X会把这些棋子分开使得他们不能攻击,问最大可以放多少棋子
题目思路:我真没想到可以用匹配来做...
我们先来想一下为什么可以用匹配来做,之后我们就记住这个行列模型,因为每一个棋子放在一个位置就霸占了该行与该列,所以我们毎放一个 棋子 就相当于把 该行与该列之间用一条线连了起来,那么其他行如果再放到与该列的交点上就不可以了..所以这就形成了匹配问题.咱们把每一行都放到一个集合S中,把每一列都放到一个集合T中,然后如果S1与T1有交点说明这个地方可以放一个棋子,将该行与该列霸占.那么S1与T1加上两点之间的连线就构成了一个二分图,我们所求的答案即为二分图的最大匹配.
随后我们想一下如何处理墙,如果没有墙的话一行即为一个,现在有墙也无所谓,相当于把 一行又分成了多行 :
如下图第一行(找了一圈没有好图就题目的图叭)
第二个格子的黑色就把第一行分成了两块,如果有一列与第二块有交点并不耽误第一块与其他列有交点.
然后如何把一行分成多行呢,我们对这个图进行染色就好了,普通染色是将图染为0与1,但是我们要处理编号所以染为 自走的编号
具体怎么染我就不说了叭(悄悄说一句遍历每一行染就完了)
最后遍历整个图只要哦 不是 'x' ,说明这个地方就是个交点,考虑列长度为1,与行长度为1,这种极限情况
最后的最后跑一遍匈牙利算法,最大匹配即为答案:
/*
代码不够精炼,匈牙利 所有二分看成boy 与 gril 比较有辨识度还有趣
*/
#include <bits/stdc++.h>
#define E 2.718
using namespace std;
typedef long long ll;
const ll INF=1e9+7;
const int maxn=1e6+8;
const double eps=1e-10;
const ll mod=1000000007;
ll n,m;
ll row[10][10],col[10][10];//染色
char mp[10][10];
int v[50][50];
int of[50];
bool vis[50];
ll cnt1,cnt;
void build()
{
cnt=1;
memset(row,-1,sizeof(row));
memset(col,-1,sizeof(col));
for(int i=1;i<=n;i++)
{
for(int k=1;k<=n;k++)
{
if(mp[i][k]=='.')
row[i][k]=cnt;
else
++cnt;
}
++cnt;
}
cnt1=1;
for(int i=1;i<=n;i++)
{
for(int k=1;k<=n;k++)
{
if(mp[k][i]=='.')
col[k][i]=cnt1;
else
++cnt1;
}
++cnt1;
}
}
bool Find(int x)
{
for(int i=1;i<=cnt1;i++)
{
if(v[x][i]&&vis[i]==false)
{
vis[i]=true;
if(!of[i]||Find(of[i]))
{
of[i]=x;
return true;
}
}
}
return false;
}
int main()
{
while(~scanf("%lld",&n)&&n)
{
for(int i=1;i<=n;i++)
scanf("%s",mp[i]+1);
//开始染***uild();
memset(of,0,sizeof(of));
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++)
if(mp[i][k]=='.')
v[row[i][k]][col[i][k]]=1;
ll sum=0;
for(int i=1;i<=cnt;i++)
{
memset(vis,0,sizeof(vis));
if(Find(i)) sum++;
}
printf("%lld\n",sum);
}
return 0;
}
总结:
1.这几天刚开始刷匹配问题,遇到好的题目,经典的题目,都要存下来发博客,便于复习.
2.再回顾一下,这个题为什么可以跑二分匹配,因为毎放一个棋子,这个棋子都会占用一行或者一列,这就说明一行匹配与一列,二分图的性质就出来了.
3.有疑问就交流!
京公网安备 11010502036488号