#include <cstdio> #include <vector> #include <unordered_map> #include <set> #include <algorithm> using namespace std; typedef pair <int, int> P; const int MAXN = 3000; const int MAXK = 4; const int MOD = 1000000007; int n, k; int result; char word[MAXN + 5]; bool t[MAXN + 5][MAXN + 5]; set <vector <int> > M; unordered_map<int,bool>::iterator it; inline int encode(int x, int y); inline P decode(int e); inline vector <int> get_neighbours(int e); void solve(int used, unordered_map<int, bool> taken, vector <int> possible); int main() { scanf("%d %d", &n, &k); for(int i = 0; i < n; ++i) { scanf("%s", word); for(int j = 0; j < n; ++j) { if(word[j] == '#') t[i + 1][j + 1] = true; } } unordered_map<int, bool> taken; vector <int> possible; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if(t[i][j]) { taken[encode(i - 1, j - 1)] = true; } else { if(t[i - 1][j] or t[i][j - 1] or t[i + 1][j] or t[i][j + 1]) { possible.push_back(encode(i - 1, j - 1)); } } } } if(k == 1) { printf("%d\n", possible.size() % MOD); } else { solve(0, taken, possible); printf("%d\n", result % MOD); } return 0; } inline int encode(int x, int y) { return n * x + y; } inline P decode(int e) { int x, y; y = e % n; x = (e - y) / n; return make_pair(x, y); } inline vector <int> get_neighbours(int e) { int x, y; P tmp = decode(e); x = tmp.first, y = tmp.second; vector <int> neighbours; if(x - 1 >= 0) neighbours.push_back(encode(x - 1, y)); if(y - 1 >= 0) neighbours.push_back(encode(x, y - 1)); if(x + 1 < n) neighbours.push_back(encode(x + 1, y)); if(y + 1 < n) neighbours.push_back(encode(x, y + 1)); return neighbours; } void solve(int used, unordered_map<int, bool> taken, vector <int> possible) { if(used == k) { vector <int> tmp; for(it = taken.begin(); it != taken.end(); ++it) { tmp.push_back((*it).first); } sort(tmp.begin(), tmp.end()); if(M.find(tmp) != M.end()) return; M.insert(tmp); result++; if(result > MOD) result %= MOD; return; } vector <int> tmp_p = possible; unordered_map<int, bool> tmp_t = taken; for(int i = 0; i < possible.size(); ++i) { int ps = possible[i]; vector <int> tmp_p = possible; unordered_map<int, bool> tmp_t = taken; swap(tmp_p[i], tmp_p[tmp_p.size()-1]); tmp_p.pop_back(); tmp_t[ps] = true; vector <int> neighbours = get_neighbours(ps); for(int i = 0; i < neighbours.size(); ++i) { int neighbour = neighbours[i]; if(tmp_t.find(neighbour) == tmp_t.end()) { tmp_p.push_back(neighbour); } } sort(tmp_p.begin(), tmp_p.end()); tmp_p.erase(unique(tmp_p.begin(), tmp_p.end()), tmp_p.end()); solve(used + 1, tmp_t, tmp_p); } }
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 112 113 114 115 116 117 118 | #include <cstdio> #include <vector> #include <unordered_map> #include <set> #include <algorithm> using namespace std; typedef pair <int, int> P; const int MAXN = 3000; const int MAXK = 4; const int MOD = 1000000007; int n, k; int result; char word[MAXN + 5]; bool t[MAXN + 5][MAXN + 5]; set <vector <int> > M; unordered_map<int,bool>::iterator it; inline int encode(int x, int y); inline P decode(int e); inline vector <int> get_neighbours(int e); void solve(int used, unordered_map<int, bool> taken, vector <int> possible); int main() { scanf("%d %d", &n, &k); for(int i = 0; i < n; ++i) { scanf("%s", word); for(int j = 0; j < n; ++j) { if(word[j] == '#') t[i + 1][j + 1] = true; } } unordered_map<int, bool> taken; vector <int> possible; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { if(t[i][j]) { taken[encode(i - 1, j - 1)] = true; } else { if(t[i - 1][j] or t[i][j - 1] or t[i + 1][j] or t[i][j + 1]) { possible.push_back(encode(i - 1, j - 1)); } } } } if(k == 1) { printf("%d\n", possible.size() % MOD); } else { solve(0, taken, possible); printf("%d\n", result % MOD); } return 0; } inline int encode(int x, int y) { return n * x + y; } inline P decode(int e) { int x, y; y = e % n; x = (e - y) / n; return make_pair(x, y); } inline vector <int> get_neighbours(int e) { int x, y; P tmp = decode(e); x = tmp.first, y = tmp.second; vector <int> neighbours; if(x - 1 >= 0) neighbours.push_back(encode(x - 1, y)); if(y - 1 >= 0) neighbours.push_back(encode(x, y - 1)); if(x + 1 < n) neighbours.push_back(encode(x + 1, y)); if(y + 1 < n) neighbours.push_back(encode(x, y + 1)); return neighbours; } void solve(int used, unordered_map<int, bool> taken, vector <int> possible) { if(used == k) { vector <int> tmp; for(it = taken.begin(); it != taken.end(); ++it) { tmp.push_back((*it).first); } sort(tmp.begin(), tmp.end()); if(M.find(tmp) != M.end()) return; M.insert(tmp); result++; if(result > MOD) result %= MOD; return; } vector <int> tmp_p = possible; unordered_map<int, bool> tmp_t = taken; for(int i = 0; i < possible.size(); ++i) { int ps = possible[i]; vector <int> tmp_p = possible; unordered_map<int, bool> tmp_t = taken; swap(tmp_p[i], tmp_p[tmp_p.size()-1]); tmp_p.pop_back(); tmp_t[ps] = true; vector <int> neighbours = get_neighbours(ps); for(int i = 0; i < neighbours.size(); ++i) { int neighbour = neighbours[i]; if(tmp_t.find(neighbour) == tmp_t.end()) { tmp_p.push_back(neighbour); } } sort(tmp_p.begin(), tmp_p.end()); tmp_p.erase(unique(tmp_p.begin(), tmp_p.end()), tmp_p.end()); solve(used + 1, tmp_t, tmp_p); } } |