6525 - Attacking rooks
Chess inspired problems are a common source of exercises in algorithms classes. Starting with the well
known 8-queens problem, several generalizations and variations were made. One of them is the N-rooks
problem, which consists of placing N rooks in an N by N chessboard in such a way that they do not
attack each other.
Professor Anand presented the N-rooks problem to his students. Since rooks only attack each other
when they share a row or column, they soon discovered that the problem can be easily solved by placing
the rooks along a main diagonal of the board. So, the professor decided to complicate the problem by
adding some pawns to the board. In a board with pawns, two rooks attack each other if and only if
they share a row or column and there is no pawn placed between them. Besides, pawns occupy some
squares, which gives an additional restriction on which squares the rooks may be placed on.
Given the size of the board and the location of the pawns, tell Professor Anand the maximum
number of rooks that can be placed on empty squares such that no two of them attack each other.
Input
The input le contains several test cases, each of them as described below.
The rst line contains an integer N (1 N 100) representing the number of rows and columns
of the board. Each of the next N lines contains a string of N characters. In the i-th of these strings,
the j-th character represents the square in the i-th row and j-th column of the board. The character
is either `.‘ (dot) or the uppercase letter `X‘, indicating respectively an empty square or a square
containing a pawn.
Output
For each test case, output a line with an integer representing the maximum number of rooks that can
be placed on the empty squares of the board without attacking each other.
Sample Input
5
X....
X....
..X..
.X...
....X
4
....
.X..
....
....
1
X
Sample Output
7
5
0
在一个n*n的图上，有一些X代表卒，让你求最多可以在多少个 . 上放車使得这些車不能相互攻击。
二分图的最大匹配，要用邻接表存，邻接矩阵的话会超时。
//0 KB 106 ms
#include<stdio.h>
#include<string.h>
#define M 1007
int link[M*10],g1[M][M],g2[M][M],head[M*10];
bool vis[M*10];
char s[M][M];
int n,a,b,num;
struct E
{
int v,next;
}edg[M*M];
void addedge(int u,int v)
{
edg[num].v=v;edg[num].next=head[u];
head[u]=num++;
}
bool find(int i)
{
for(int j=head[i]; j!=-1; j=edg[j].next)
{
int v=edg[j].v;
if(!vis[v])
{
vis[v]=true;
if(!link[v]||find(link[v]))
{
link[v]=i;
return true;
}
}
}
return false;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(head,-1,sizeof(head));
num=0;
memset(link,0,sizeof(link));
int count=0;
for(int i=1; i<=n; i++)
scanf("%s",s[i]+1);
a=1,b=1;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(s[i][j]==‘.‘)
{
g1[i][j]=s[i][j-1]!=s[i][j]?a++:g1[i][j-1];
g2[i][j]=s[i-1][j]!=s[i][j]?b++:g2[i-1][j];
}
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(s[i][j]==‘.‘)addedge(g1[i][j],g2[i][j]);
for(int i=1; i<a; i++)
{
memset(vis,false,sizeof(vis));
if(find(i))count++;
}
printf("%d\n",count);
}
return 0;
}
UVALive 6525 Attacking rooks,布布扣,bubuko.com
UVALive 6525 Attacking rooks
原文：http://blog.csdn.net/crescent__moon/article/details/25074937
