这里我居然能自己想想到怎么建图匹配,很是不容易...
题意:这里有一片油田,但是不是纯净的,有的地方是水,现在有一个捞石油的机器,但是这个机器捞的范围是固定的,是2*1的一个矩形大小,那么对于整个油田打捞,也只能打捞2*1的地方,那么,最多可以打捞多少?
分析:
这里对于图中每一个‘#’,我们就遍历四周有没有‘#’,如果有,那么这个'#'就可以和旁边的‘#‘就可以匹配,但是这里的图中都是字符,我们就先遍历一次,对于每个'#'编号,然后建图,这里我的处理方式是从上到下,从左到右,对于每一个’#‘,就只看右边和下边有没有’#‘,然后建双向边,实际上和对于每个点,向四个方向找'#'是一样的
那么直接上马
//296MS 4576K
#include<stdio.h>
#include<string.h> #define MAX 601 struct Edge
{
int to,next;
}edge[MAX*MAX];
int head[MAX*MAX],tol;
void add(int a,int b)
{
edge[tol].to = b;
edge[tol].next = head[a];
head[a] = tol ++;
} char map[MAX][MAX];
int sum,QQ[MAX][MAX];
int vis[2][2]={{1,0},{0,1}}; int link[MAX*MAX],flag[MAX*MAX]; bool dfs(int u)
{
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(!flag[v])
{
flag[v] = 1;
if(link[v] == -1 || dfs(link[v]))
{
link[v] = u;return true;
}
}
}
return false;
} int match()
{
int ans = 0;
memset(link,-1,sizeof(link));
for(int u = 0; u < sum; u ++)
{
memset(flag,0,sizeof(flag));
if(dfs(u)) ans ++;
}
return ans/2;
} int main()
{
int i,j;
int T,N;
scanf("%d",&T);
for(int cas = 1; cas <= T; cas ++)
{
tol = 0;
sum = 0;
memset(head,-1,sizeof(head));
scanf("%d",&N);
for(i = 0; i < N; i ++,getchar())
scanf("%s",map[i]); //建图
for(i = 0; i < N; i++)
for(j = 0; j < N; j ++)
if(map[i][j] == '#')
QQ[i][j] = sum++;//map[i][j] = sum ++ +'0';这样不可以,如果超过9,10这个不是一个字符啦....只能借助一个数组
for(i = 0; i < N; i ++)
for(j = 0; j < N; j ++)
{
if(map[i][j] != '.')
for(int k = 0; k < 4; k ++)
{
int x = i + vis[k][0],y = j + vis[k][1];
if(y >= 0 && y < N && x >= 0 && x < N && map[x][y] != '.')// 等价map[x][y] == '#'
add(QQ[i][j], QQ[x][y]),add(QQ[x][y], QQ[i][j]);
}
}
printf("Case %d: %d\n",cas,match());
}
return 0;
}
个人愚昧观点,欢迎指正和讨论