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
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>


const int MAXN = 3100;
const int MAX = MAXN * MAXN;
const int MOD = 1e9 + 7;
int n, k;
int available[MAX];
std::vector<int> used;
int aCnt;
char row[MAXN][MAXN];
std::set<std::vector<int> > sol;


int brutal(int aCnt, int i = 0, int m = 0) {
	if (m == 0) {
		used.resize(k);
	}

	while (i < aCnt) {
		int x = available[i] % n;
		int y = available[i] / n;

		used[m] = y * n + x;

		if (m + 1 == k) {
			std::vector<int> key;
			key = used;
			std::sort(key.begin(), key.end());
			sol.insert(key);
		} else {
			row[y][x] = '#';

			int a = aCnt;
			// can add multiple times, no worries
			if (y > 0 && row[y - 1][x] == '.') {
				available[a++] = (y - 1) * n + x;
			}
			if (x > 0 && row[y][x - 1] == '.') {
				available[a++] = y * n + x - 1;
			}
			if (y < n - 1 && row[y + 1][x] == '.') {
				available[a++] = (y + 1) * n + x;
			}
			if (x < n - 1 && row[y][x + 1] == '.') {
				available[a++] = y * n + x + 1;
			}

			brutal(a, i + 1, m + 1);

			row[y][x] = '.';
		}
		i++;
	}

	return (m == 0 ? (sol.size() % MOD) : -1);
}

int main(int argc, char *argv[]) {
	scanf("%i%i", &n, &k);

	for (int y = 0; y < n; y++) {
		scanf("%s", row[y]);
	}
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			if (row[y][x] == '.') {
				if (y > 0 && row[y - 1][x] == '#' ||
					x > 0 && row[y][x - 1] == '#' ||
					y < n - 1 && row[y + 1][x] == '#' ||
					x < n - 1 && row[y][x + 1] == '#') {
					available[aCnt++] = y * n + x;
				}
			}
		}
	}

	auto ret = brutal(aCnt);

	printf("%i\n", ret);

	return 0;
}