#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 3e3+5; bool av[MAXN][MAXN]; int res = 0, n, k, p = 997, ruch[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; ll mod1 = 1e9+7, mod2 = 1e9+9; unordered_set<ll> S; void f(int lvl) { ll h1 = 0, h2 = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { int x = av[i][j] + 1; h1 = (h1*p + x)%mod1; h2 = (h2*p + x)%mod2; } } if (S.count(h1*h2) != 0) return; else if (lvl == k) { res++; S.insert(h1*h2); return; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (av[i][j]) { for (int l = 0; l < 4; l++) { int x = i + ruch[l][0], y = j + ruch[l][1]; if (x == 0 || x > n || y == 0 || y > n) continue; if (!av[x][y]) { av[i][j] = 0; f(lvl+1); av[i][j] = 1; break; } } } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { char c; cin >> c; av[i][j] = (c == '.'); } } if (k == 1) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (av[i][j]) { for (int l = 0; l < 4; l++) { int x = i+ruch[l][0], y = j+ruch[l][1]; if (x < 0 || x > n || y < 0 || y > n) continue; if (!av[x][y]) res++; } } } } } else f(0); cout << res << "\n"; }
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; using ll = long long; const int MAXN = 3e3+5; bool av[MAXN][MAXN]; int res = 0, n, k, p = 997, ruch[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; ll mod1 = 1e9+7, mod2 = 1e9+9; unordered_set<ll> S; void f(int lvl) { ll h1 = 0, h2 = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { int x = av[i][j] + 1; h1 = (h1*p + x)%mod1; h2 = (h2*p + x)%mod2; } } if (S.count(h1*h2) != 0) return; else if (lvl == k) { res++; S.insert(h1*h2); return; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (av[i][j]) { for (int l = 0; l < 4; l++) { int x = i + ruch[l][0], y = j + ruch[l][1]; if (x == 0 || x > n || y == 0 || y > n) continue; if (!av[x][y]) { av[i][j] = 0; f(lvl+1); av[i][j] = 1; break; } } } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { char c; cin >> c; av[i][j] = (c == '.'); } } if (k == 1) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (av[i][j]) { for (int l = 0; l < 4; l++) { int x = i+ruch[l][0], y = j+ruch[l][1]; if (x < 0 || x > n || y < 0 || y > n) continue; if (!av[x][y]) res++; } } } } } else f(0); cout << res << "\n"; } |