游客 注册 | 登录
中文 | En

2449 - E：远古石门机关

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

有一个远古石门，上面的机关是由n行m列格子组成。其中，凸起的格子是灰色的。每一次操作可以让其中一行或一列中凸起的格子全部按下。只有使用了最小次数的操作，石门才会打开，否则机关会复位。给定一个这样的机关，多少次操作才能打开石门呢？

题目输入

输入数据的第一行是一个整数T，表示有T组测试样例，接着是T行数据，每行两个整数n和m，分别表示机关格子的行数和列数。接着是个n行m列的矩阵，其中1表示格子是凸起的，0表示格子是按下的。T<=50，0<n,m<100。

<br />

题目输出

对于每组测试样例，输出打开石门的操作数并独占一行。

输入/输出样例

输入格式

2
4 4
0000
0101
0000
0100
3 3
111
010
000

输出格式

2
2

C++解答

#include<stdio.h>
#include<string.h>
int n,m,map[201][201],flag[201],p[201];
char a[201][201];
int dfs(int x)
{
	int i;
	for(i=0;i<n+m;i++)
		if(map[x][i]&&flag[i]==0)
		{
			flag[i]=1;
			if(p[i]==-1||dfs(p[i]))
			{
				p[i]=x;
				return 1;
			}
		}
		return 0;
}
int main()
{
    int i,j,s,x,y,T;
	scanf("%d",&T);
    while(T--)
    {
		scanf("%d%d%*c",&n,&m);
		memset(map,0,sizeof(map));
		memset(p,-1,sizeof(p));
		for(i=0;i<n;i++)
		{
			scanf("%s",a[i]);
			for(j=0;j<m;j++)
				if(a[i][j]=='1')
					map[i][n+j]=map[n+j][i]=1;
		}
		for(i=0,s=0;i<n+m;i++)
		{
			memset(flag,0,sizeof(flag));
			if(dfs(i))
				s++;
		}
		printf("%d\n",s/2);
	}
    return 0;
}
请先登陆