#include<bits/stdc++.h> using namespace std; #define mp make_pair #define fi first #define se second const int N = 3002; const long long INF = 30000000; char s[N][N]; int di[4] = {0, 0, 1, -1}; int dj[4] = {1, -1, 0, 0}; int wynik = 0, n; struct czworki { int a, b, c, d; }; map<pair<pair<pair<int, int>, int>, int>, int> m; void bfs(int i, int j, int k, vector<long long> v) { if(k-1==0) { long long t[4]; for(int w = 0; w < k; w++) t[w] = v[w]; for(int w = k; w < 4; w++) t[w] = -1; sort(t, t+4); pair<pair<pair<int, int>, int>, int> cw; cw.fi.fi.fi = t[0]; cw.fi.fi.se = t[1]; cw.fi.se = t[2]; cw.se = t[3]; if(!m[cw]) wynik++; m[cw] = true; return; } for(int w = 0; w < 4; w++) { int x = i+di[w]; int y = j+dj[w]; if(x<0 or x==n or y<0 or y==n) continue; v.push_back((long long)(x)*INF+(long long)y); bfs(x, y, k-1, v); v.pop_back(); } } int main() { int k; scanf("%d%d", &n, &k); for(int i = 0; i < n; i++) scanf("%s", s[i]); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { vector<long long> v; if(s[i][j]=='#') bfs(i, j, k, v); } } printf("%d\n", wynik); }
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 | #include<bits/stdc++.h> using namespace std; #define mp make_pair #define fi first #define se second const int N = 3002; const long long INF = 30000000; char s[N][N]; int di[4] = {0, 0, 1, -1}; int dj[4] = {1, -1, 0, 0}; int wynik = 0, n; struct czworki { int a, b, c, d; }; map<pair<pair<pair<int, int>, int>, int>, int> m; void bfs(int i, int j, int k, vector<long long> v) { if(k-1==0) { long long t[4]; for(int w = 0; w < k; w++) t[w] = v[w]; for(int w = k; w < 4; w++) t[w] = -1; sort(t, t+4); pair<pair<pair<int, int>, int>, int> cw; cw.fi.fi.fi = t[0]; cw.fi.fi.se = t[1]; cw.fi.se = t[2]; cw.se = t[3]; if(!m[cw]) wynik++; m[cw] = true; return; } for(int w = 0; w < 4; w++) { int x = i+di[w]; int y = j+dj[w]; if(x<0 or x==n or y<0 or y==n) continue; v.push_back((long long)(x)*INF+(long long)y); bfs(x, y, k-1, v); v.pop_back(); } } int main() { int k; scanf("%d%d", &n, &k); for(int i = 0; i < n; i++) scanf("%s", s[i]); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { vector<long long> v; if(s[i][j]=='#') bfs(i, j, k, v); } } printf("%d\n", wynik); } |