首页 > ACM题库 > HDU-杭电 > HDU 3160-Rooks[解题报告]HOJ
2014
03-06

HDU 3160-Rooks[解题报告]HOJ

Rooks

问题描述 :


"Ancient" Calculator

You have unexpectedly become the owner of a large chessboard, having fifteen squares to each side. Because you do not know how to play chess on such a large board, you find an alternative way to make use of it.

In chess, a rook attacks all squares that are in the same row or column of the chessboard as it is. For the purposes of this problem, we define a rook as also attacking the square on which it is already standing.

Given a set of chessboard squares, how many rooks are needed to attack all of them?

输入:

Input consists of a number of test cases. Each test case consists of fifteen lines each containing fifteen characters depicting the chess board. Each character is either a period (.) or a hash (#). Every chessboard square depicted by a hash must be attacked by a rook. After all the test cases, one more line of input appears. This line contains the word END.

输出:

Input consists of a number of test cases. Each test case consists of fifteen lines each containing fifteen characters depicting the chess board. Each character is either a period (.) or a hash (#). Every chessboard square depicted by a hash must be attacked by a rook. After all the test cases, one more line of input appears. This line contains the word END.

样例输入:

...............
...............
...............
...............
...............
...............
...............
.......#.......
...............
...............
...............
...............
...............
...............
...............
END

样例输出:

1

#include<cstdio>
#include<cstring>
#define clr(a) memset(a,0,sizeof(a))
#define min(a,b) (a)<(b)?(a):(b)
#define max(a,b) (a)>(b)?(a):(b)
char qi[16][16];
int sum(int s)
{
	int sum=0;
	while(s)
	{
		if(s%2) sum++;
		s/=2;
	}
	return sum;
}
int play()
{
	int i,j;
	scanf("%s",qi[0]);
	if(qi[0][0]=='E') return 0;
	for(i=1;i<15;++i)
	{
		scanf("%s",qi[i]);
	}
	int s,f[15],ans=0x3f3f3f3f;
	for(s=0;s<(1<<15);++s)
	{
		clr(f);
		int tmp=0;
		for(i=0;i<15;++i)
		{
			if((s&(1<<i))==0)
			{
				for(j=0;j<15;++j)
				{
					if(qi[i][j]=='#')
						f[j]=1;
				}
			}
		}
		for(i=0;i<15;++i)
			tmp+=f[i];
		ans=min(max(tmp,sum(s)),ans);
	}
	printf("%d\n",ans);
	return 1;
}

int main()
{
	while(play());
	return 0;
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。