1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>

using namespace std;

//#define mod 10000000009;

bool tab[3010][3010];

pair<int, int> kier[] { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };

struct moj {
    pair<short int, short int> x[4];
    moj() {
        for( int i=0; i<4; i++ ) {
            x[i] = {0, 0};
        }
    }

    bool operator < ( const moj & other ) const {
        for( int i=0; i<4; i++ ) {
            if( x[i] != other.x[i] ) return x[i] < other.x[i];
        }
        return 0;
    }
};

moj pom;
vector<moj> wy;

int n;

void algo( int k ) {
    bool czy;
    for( int i=1; i<=n; i++ ) {
        for( int j=1; j<=n; j++ ) {
            if( tab[i][j] == 0 ) {
                czy = 0;
                for( auto & a : kier ) {
                    if( tab[i+a.first][j+a.second] ) {
                        czy = 1;
                        break;
                    }
                }
                if( !czy ) continue;
                pom.x[k] = {i, j};
                if( k ) {
                    tab[i][j] = 1;
                    algo( k-1 );
                    tab[i][j] = 0;
                } else {
                    wy.push_back( pom );
                }
            }
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio( 0 );
    cin.tie( 0 );

    int k;
    cin >> n >> k;
    k--;
    for( int i=1; i<=n; i++ ) {
        char a;
        for( int j=1; j<=n; j++ ) {
            cin >> a;
            if( a=='#' ) tab[i][j] = 1;
        }
    }
    algo( k );
    for( auto & i : wy ) {
        sort( i.x, i.x+4 );
    }
    sort( wy.begin(), wy.end() );
    int res = 1;
    for( int i=1; i<wy.size(); i++ ) {
        /*for( int j=0; j<4; j++ ) {
            cout << wy[i].x[j].first << " " << wy[i].x[j].second << "   ";
        }
        cout << "\n";*/
        if( wy[i] < wy[i-1] || wy[i-1] < wy[i] ) res++;
    }
    cout << res;

    return 0;
}