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
#include <bits/stdc++.h>

int result = 0;

struct Punkt{
    int x;
    int y;
};

bool maSasiada(std::vector <std::vector<char> > plansza, Punkt pos, int n){
    int x = pos.x;
    int y = pos.y;

    if (y > 0 && plansza[y-1][x] == '#')
        return true;
    if (x > 0 && plansza[y][x-1] == '#')
        return true;
    if (x < n-1 && plansza[y][x+1] == '#')
        return true;
    if (y < n-1 && plansza[y+1][x] == '#')
        return true;
    return false;
}

void licz(std::vector <Punkt> pos, std::vector <std::vector<char> > plansza, int i, int h, int k, int n){
    if (h == k){
        result++;
        //std::cout << "KONIEC\n";
        return;
    }
    int x = pos[i].x;
    int y = pos[i].y;
    plansza[y][x] = '#';
    for (int j = i+1; j < pos.size(); j++){
        if (maSasiada(plansza, pos[j], n)){
            //std::cout << "WCHODZE W " << pos[j].y << ", " << pos[j].x << "\n";
            licz(pos, plansza, j, h+1, k, n);
        }
    }
    return;
}

int main(){
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);
    int n, k; // wymiary, liczba ruchow do przodu
    std::cin >> n >> k;
    std::vector <std::vector<char> > plansza;
    std::vector <Punkt> pos;
    char x;
    std::vector <char> linia;
    for (int i = 0; i < n; i++){
        linia.clear();
        for (int j = 0; j < n; j++){
            std::cin >> x;
            linia.push_back(x);
            if (x == '.'){
                Punkt p1;
                p1.y = i;
                p1.x = j;
                pos.push_back(p1);
            }
        }
        plansza.push_back(linia);
    }
    int h = 0;
    for (int i = 0; i < pos.size(); i++){
        h = 1;
        if (maSasiada(plansza, pos[i], n)){
            //std::cout << "WCHODZE W " << pos[i].y << ", " << pos[i].x << "\n";
            licz(pos, plansza, i, h, k, n);
        }
    }
    std::cout << result << "\n";
}