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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <vector>
#include<deque>
#include<unordered_map>
#include <set>
#include <iostream>

using namespace std;

bool isFull[3001][3001];

struct C {
    vector<int> v;
    C(vector<int> k){
        sort(k.begin(),k.end());
        for(auto i=k.begin();i!=k.end();i++){
            v.push_back(*i);
        }
    }
};

struct CHash {
 std::size_t operator()(const C& k) const
 {
     int hash = 0;
     for(int i=0;i<k.v.size();i++){
         hash+=k.v[i]*(i+1);
     }
     return hash;
 }
};

struct CEqual {
 bool operator()(const C& lhs, const C& rhs) const
 {
    bool isEqual = true;
    for(int i = 0;i!=lhs.v.size();i++){
        if(lhs.v[i]!=rhs.v[i]) isEqual = false;
    }
    return isEqual;
 }
};

unordered_map<C,int,CHash,CEqual> M;



void funkcja(vector<pair<int,int>> V,set<pair<int,int>> used,int poziom, int k,vector<int> last,int n,pair<int,int> acc){
    //printf("%d %d\n",acc.first,acc.second);
    //printf("poziom: %d last: %d\n\n",poziom,last);
    //int tmp =(n*acc.first)+acc.second;
    //tmp*=(poziom+1);
    last.push_back((n*acc.first)+acc.second);
    //for(int i=0;i<last.size();i++) printf("%d ",last[i]);
    //printf("\n");
    if(poziom==k-1) M[C(last)]=1;
    else{
        vector<pair<int,int>> sasiady;
        if(acc.first>0 && !isFull[acc.first-1][acc.second] && used.count(make_pair(acc.first-1,acc.second))==0) {
            pair<int,int> sasiad = make_pair(acc.first-1,acc.second);
            V.push_back(sasiad);
            /*used.insert(sasiad);
            funkcja(V,used,poziom+1,k,last,n,sasiad);
            V.pop_back();
            auto it = used.find(sasiad);
            used.erase(it,++it);*/
            sasiady.push_back(sasiad);
        }
        if(acc.first<(n-1) && !isFull[acc.first+1][acc.second] && used.count(make_pair(acc.first+1,acc.second))==0) {
            pair<int,int> sasiad = make_pair(acc.first+1,acc.second);
            V.push_back(sasiad);
            /*used.insert(sasiad);
            funkcja(V,used,poziom+1,k,last,n,sasiad);
            V.pop_back();
            auto it = used.find(sasiad);
            used.erase(it,++it);*/
            sasiady.push_back(sasiad);
        }
        if(acc.second>0 && !isFull[acc.first][acc.second-1] && used.count(make_pair(acc.first,acc.second-1))==0) {
            pair<int,int> sasiad = make_pair(acc.first,acc.second-1);
            V.push_back(sasiad);
            /*used.insert(sasiad);
            funkcja(V,used,poziom+1,k,last,n,sasiad);
            V.pop_back();
            auto it = used.find(sasiad);
            used.erase(it,++it);*/
            sasiady.push_back(sasiad);
        }
        if(acc.second<(n-1) && !isFull[acc.first][acc.second+1] && used.count(make_pair(acc.first,acc.second+1))==0) {
            pair<int,int> sasiad = make_pair(acc.first,acc.second+1);
            V.push_back(sasiad);
            /*used.insert(sasiad);
            funkcja(V,used,poziom+1,k,last,n,sasiad);
            V.pop_back();
            auto it = used.find(sasiad);
            used.erase(it,++it);*/
            sasiady.push_back(sasiad);
        }

        for(auto sas=sasiady.begin();sas!=sasiady.end();sas++){
            used.insert(*sas);
            funkcja(V,used,poziom+1,k,last,n,*sas);
            auto it = used.find(*sas);
            used.erase(it,++it);
        }

        for(auto p = V.begin();p!=V.end();p++){
            pair<int,int> pp = *p;
            if(used.count(pp)==0){
                used.insert(pp);
                funkcja(V,used,poziom+1,k,last,n,pp);
                auto it = used.find(pp);
                used.erase(it,++it);
            }
        }

    }
}

int main(){
    int n,k;
    scanf("%d %d",&n,&k);

    string tmp;
    for(int i=0;i<n;i++){
        cin >> tmp;
        for(int j=0;j<n;j++){
            if(tmp[j]=='#') isFull[i][j]=true;
            else isFull[i][j]=false;
        }
    }
    vector<pair<int,int>> V;
    set<pair<int,int>> s;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!isFull[i][j]){
                if((i>0 && isFull[i-1][j]) || (j>0 && isFull[i][j-1]) || (i<(n-1) && isFull[i+1][j]) || (j<(n-1) && isFull[i][j+1])){
                    V.push_back(make_pair(i,j));
                }
            }
        }
    }

    vector<int> P;
    for(auto i=V.begin();i!=V.end();++i){
        s.insert(*i);
        funkcja(V,s,0,k,P,n,*i);
    }
    printf("%d\n",M.size());
   // for(auto m=M.begin();m!=M.end();m++) printf("%d ",m->first);

}
//Author: Helena Borak