2015
07-16

# Where is the King

There is a King placed on an N * N chessboard. In each second, Bob must move the King to the next cell in one of the eight directions, but he can not move the King to the outside of the chessboard, and can not move the King to a damaged cell. Note: If and only if there is not any next cell that he can place the King on in the eight directions, the King will stay in the same cell.
Now your task is to calculate that, after T seconds, the number of the cells that the King could be on.

There is an integer C (1 <= C <= 500) in the first line, indicates there are C test cases in total.
For each test case, there are four integers N (2 <= N <= 100), T (1 <= T <= 1000000000), X (1 <= X <= N), Y (1 <= Y <= N). N and T have the same meaning as above, (X, Y) indicates the King’s initial location. Then there are N lines. In each line, there is a string with N characters include “#” and “.”, which indicates the states of the cells in this row. “#” means this cell is damaged, and “.” means this cell is ordinary. You can assume (X, Y) is an ordinary cell.
For the coordinate (x, y), it stands for the cell in row x and column y. The coordinate of the top-left cell is (1, 1), and the coordinate of the bottom-right cell is (N, N).

There is an integer C (1 <= C <= 500) in the first line, indicates there are C test cases in total.
For each test case, there are four integers N (2 <= N <= 100), T (1 <= T <= 1000000000), X (1 <= X <= N), Y (1 <= Y <= N). N and T have the same meaning as above, (X, Y) indicates the King’s initial location. Then there are N lines. In each line, there is a string with N characters include “#” and “.”, which indicates the states of the cells in this row. “#” means this cell is damaged, and “.” means this cell is ordinary. You can assume (X, Y) is an ordinary cell.
For the coordinate (x, y), it stands for the cell in row x and column y. The coordinate of the top-left cell is (1, 1), and the coordinate of the bottom-right cell is (N, N).

3
3 1 3 3
...
...
...
3 2 3 3
...
..#
.#.
3 4 1 3
.#.
.##
...

3
6
1
Hint
For Sample 1, the blue cells in the left picture of the Figure 1 show the cells that the King could be on after 1 second.
For Sample 2, the blue cells in the right picture of the Figure 1 show the cells that the King could be on after 2 seconds.
The red cells stand for the damaged cells, and the yellow cells shows other ordinary cells.



#include<cstdio>
#include<stack>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 99999999
int dp[(1<<21)+5],score[(1<<21)+5],g,b,s,x,y;
int bag[25][20];
void cal(){
int sum[11];
for(int i=0;i<(1<<b);++i){
memset(sum,0,sizeof sum);
for(int j=0;j<b;++j){
if(i>>j&1){
for(int k=1;k<=g;++k)sum[k]+=bag[j][k];
}
}
for(int j=1;j<=g;++j)score[i]+=sum[j]/s;
}
}

int dfs(int cur){
if(dp[cur]!=-inf)return dp[cur];

for(int j=0;j<b;++j)
if(!(cur&(1<<j))){
int res=score[cur|(1<<j)]-score[cur];
if(res>0){
dp[cur]=max(dp[cur],dfs(cur|(1<<j))+res);
}else{
dp[cur]=max(-dfs(cur|(1<<j)),dp[cur]);
}
}

return dp[cur];
}

void solve(){
memset(bag,0,sizeof bag);
memset(score,0,sizeof score);
for(int i=0;i<b;++i){
scanf("%d",&x);
while(x--){
scanf("%d",&y);
bag[i][y]++;
}
}
cal();
for(int i=0;i<(1<<b);++i)dp[i]=-inf;
dp[(1<<b)-1]=0;
printf("%d\n",dfs(0));
}
int main(){
while(~scanf("%d%d%d",&g,&b,&s),g+b+s){
solve();
}
return 0;
}