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
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#define ll long long
using namespace std;
ll n2, n, k, e, siz=0; pair <int,int> M1[4], Moves[4], Neigh[] = {{0,1},{0,-1},{1,0},{-1,0}}; bool Taken[3002][3002];
void gen(int k1, vector < pair <int,int> > &Tiles, vector <ll> &V)
{
    if(k1==k){
        for(int i=0; i<k; i++)
            M1[i] = Moves[i];
        sort(&M1[0],&M1[k]);
        ll cur=0;
        for(int i=0; i<k; i++)
            cur=cur*n2+n*M1[i].first+M1[i].second;
        V.push_back(cur);
    }
    else {
        int i1, j1; set < pair <int,int> > Used;
        for(int i=0; i<e+4*k1; i++){
                //i1 = Tiles[i].first+Neigh[j].first, j1 = Tiles[i].second+Neigh[j].second;
                i1 = Tiles[i].first, j1 = Tiles[i].second;
                if(!Taken[i1][j1] && Used.find({i1,j1})==Used.end()){
                    Used.insert({i1,j1});
                    Taken[i1][j1]=true;
                    Moves[k1]={i1,j1};
                    for(int j=0; j<4; j++)
                        Tiles[e+4*k1+j]={i1+Neigh[j].first,j1+Neigh[j].second};
                    gen(k1+1,Tiles,V);
                    Taken[i1][j1]=false;
                }
        }
    }
}

void gen1(int k1, vector < pair <int,int> > &Tiles, vector < pair <ll,ll> > &V)
{
    if(k1==k){
        for(int i=0; i<k; i++)
            M1[i] = Moves[i];
        sort(&M1[0],&M1[k]);
        ll cur=0, cur1=0;
        for(int i=0; i<2 && i<k; i++)
            cur=cur*n2+n*M1[i].first+M1[i].second;
        for(int i=2; i<k; i++)
            cur1=cur1*n2+n*M1[i].first+M1[i].second;
        V.push_back({cur,cur1});
    }
    else {
        int i1, j1; set < pair <int,int> > Used;
        for(int i=0; i<e+4*k1; i++){
                //i1 = Tiles[i].first+Neigh[j].first, j1 = Tiles[i].second+Neigh[j].second;
                i1 = Tiles[i].first, j1 = Tiles[i].second;
                if(!Taken[i1][j1] && Used.find({i1,j1})==Used.end()){
                    Used.insert({i1,j1});
                    Taken[i1][j1]=true;
                    Moves[k1]={i1,j1};
                    for(int j=0; j<4; j++)
                        Tiles[e+4*k1+j]={i1+Neigh[j].first,j1+Neigh[j].second};
                    gen1(k1+1,Tiles,V);
                    Taken[i1][j1]=false;
                }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin >> n >> k;
    n2 = n*n;
    vector <string> Table(n);
    for(int i=0; i<n; i++)
        cin >> Table[i];
    vector < pair <int,int> > Tiles;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++){
            Taken[i+1][j+1] = (Table[i][j]=='#');
            if(Table[i][j]=='#'){
                Tiles.push_back({i+1,j+1});
                siz++;
            }
        }
    for(int i=0; i<=n+1; i++)
        Taken[0][i]=Taken[n+1][i]=Taken[i][0]=Taken[i][n+1]=true;
    vector < pair <int,int> > W;
    for(int i=0; i<siz; i++)
        for(int j=0; j<4; j++)
            W.push_back({Tiles[i].first+Neigh[j].first,Tiles[i].second+Neigh[j].second});
    sort(W.begin(),W.end());
    e = unique(W.begin(),W.end()) - W.begin();
    for(int i=0; i<16; i++)
        W.push_back({0,0});

    if(n<=200){
        vector <ll> V;
        V.reserve(n2);
        gen(0,W,V);
        sort(V.begin(),V.end());
        cout << unique(V.begin(),V.end())-V.begin() << "\n";
    }
    else {
        vector < pair <ll,ll> > V;
        V.reserve(n2);
        gen1(0,W,V);
        sort(V.begin(),V.end());
        cout << unique(V.begin(),V.end())-V.begin() << "\n";
    }
    return 0;
}