2014
03-06

# Rooks

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。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。