学步园

#include <stdio.h>
#include <memory.h>

//二分图 最大匹配度 匈牙利算法
//Bipartite graph, maximum matching,  Hungarian algorithm
#define X_MAX_GRID_NUM	4
#define Y_MAX_GRID_NUM	4
#define X_MAX_POINT_NUM (X_MAX_GRID_NUM*(Y_MAX_GRID_NUM+1)/2)
#define Y_MAX_POINT_NUM (Y_MAX_GRID_NUM*(X_MAX_GRID_NUM+1)/2)

int  gXnum = 0;
int  gYnum = 0;
bool gLine[X_MAX_POINT_NUM*4][Y_MAX_POINT_NUM*4];	// g[x][y] 表示点x, y之间是否有连线。 x表示X点集 y表示Y点集
bool gY[Y_MAX_POINT_NUM*4];							// gY[y] 表示Y集合点y是否在该次
int  gYX[Y_MAX_POINT_NUM*4];						// gYX[y]表示点Y连接的是X集合的哪一点

bool MoreMatch(int x)
{
	for (int y = 0; y < gYnum; y++)
	{
		if(gLine[x][y] && !gY[y])
		{
			gY[y] = true;
			if(gYX[y] == 0 || MoreMatch(gYX[y]))
			{
				gYX[y] = x;
				return true;
			}
		}
	}
	return false;
}

int GetBiGraphMaximumMatching()
{
	int iRet = 0;
	for (int x = 0; x < gXnum; x++)
	{
		memset(gY, 0, sizeof(gY));
		if(MoreMatch(x))
		{
			iRet++;
		}
	}
	return iRet;
}

// 数据建模

char gInput[X_MAX_GRID_NUM][Y_MAX_GRID_NUM+1];
int  gX2Point[X_MAX_GRID_NUM][Y_MAX_GRID_NUM];

int main()
{
	int gridNum = 0;
	scanf("%d", &gridNum);
	while(gridNum != 0)
	{
		memset(gLine, 0, sizeof(gLine));
		memset(gYX, 0, sizeof(gYX));

		// 第一行，最后一行，不增加行
		// 第一列，最后一列，不增加列
		for (int x = 0; x < gridNum; x++)
		{
			scanf("%s", gInput[x]);
			for (int y = 0; y < gridNum; y++)
			{
				if (gInput[x][y] == 'X')
				{
					gX2Point[x][y] = -1;
					if(y > 0 && gInput[x][y-1] != 'X')
					{
						gYnum++;
					}
					continue;
				}
				gX2Point[x][y] = gYnum;
			}

			if(gInput[x][gridNum-1] != 'X')
			{
				gYnum++;
			}
		}

		for (int y = 0; y < gridNum; y++)
		{
			for (int x = 0; x < gridNum; x++)
			{
				if (gInput[x][y] == 'X')
				{
					if(x > 0 && gInput[x-1][y] != 'X')
					{
						gXnum++;
					}
					continue;
				}
				gLine[gXnum][gX2Point[x][y]]=true;
			}

			if(gInput[gridNum-1][y] != 'X')
			{
				gXnum++;
			}
		}

		printf("%d\n", GetBiGraphMaximumMatching());

		scanf("%d", &gridNum);
	}
}