看电影

Description

   wjh要去看电影，邀请了lmb,xxb,cly,yzj,ckx等人，最后有k个人同意一起去。要去的电影院的位置是矩阵型的，其中’#’表示已经被人预定了，’*’表示空位，他们打算挑同一行或者同一列连续的座位坐在一起，现在给出k和位置的预定请况，试问有几种坐位置的方法。

Input

 第一行输入两个数n和k，n表示电影院的位置是n*n的。（0<n<=10,0<=k<10）

接下在n行，每行n个字符，表示位置的预订情况。

Output

 一行输出有几种坐法。

Sample Input

4 1 **## *### #### ####

Sample Output

4

HINT

 如所示样例，用w表示wjh，用l表示另一人，四种坐法如下：

wl##

*###

####

####

lw##

*###

####

####

w*##

l###

####

####

l*##

w###

####

####

题解

很简单暴力纵向横向都搜索一下就是了，注意当k为0（即只有wjh一个人的时候）答案要除以2

#include<bits/stdc++.h>
using namespace std;
char s[108][108];
int main(){
    freopen("data10.in","r",stdin);
    freopen("data10.out","w",stdout);
    int n,k;
    scanf("%d%d",&n,&k);
    k++;
    for(int i=0;i<n;i++){
        scanf("%s",s[i]);
    }
    int ans=0;
    for(int i=0;i<n;i++){
        int sum=0;
        for(int j=0;j<n;j++){
            if(s[i][j]=='#'){
                if(sum>=k){
                    ans+=sum-k+1;
                }
                sum=0;
            }
            else{
                sum++;
            }
        }
        if(sum>=k){
            ans+=sum-k+1;
        }
    }
    for(int i=0;i<n;i++){
        int sum=0;
        for(int j=0;j<n;j++){
            if(s[j][i]=='#'){
                if(sum>=k){
                    ans+=sum-k+1;
                }
                sum=0;
            }
            else{
                sum++;
            }
        }
        if(sum>=k){
            ans+=sum-k+1;
        }
    }
    if(k==1) ans/=2;
    int c=1;
    for(int i=1;i<=k;i++){
        c*=i;
    }
    ans*=c;
    printf("%d\n",ans);
}