hdu4185解题报告

这里我居然能自己想想到怎么建图匹配，很是不容易...

题意：这里有一片油田，但是不是纯净的，有的地方是水，现在有一个捞石油的机器，但是这个机器捞的范围是固定的，是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;

}

个人愚昧观点，欢迎指正和讨论