#include<cstdio> #include<vector> #include<set> #include<algorithm> int n,k; bool ** t; std::set<std::vector<int> > results; void print_array() { for (int r = 0; r < n; r ++) { for (int c = 0; c < n; c++) { printf("%d", t[c][r]); } printf("\n"); } } void input() { scanf("%d %d", &n, &k); t = new bool * [n]; for (int i = 0; i < n; i++) { t[i] = new bool[n]; } char * q = new char[n]; for (int r = 0; r < n; r++) { scanf("%s", q); for (int c = 0; c < n; c++) { t[c][r] = (q[c] == '#'); } } //print_array(); } bool get_if_in_range(int x, int y) { // true = occupied if (x >= 0 && x < n && y >= 0 && y < n) { return t[x][y]; } return false; } bool has_neighbour(int x, int y) { //print_array(); bool res = get_if_in_range(x - 1, y) || get_if_in_range(x, y - 1) || get_if_in_range(x + 1, y) || get_if_in_range(x, y + 1); //printf("has_neighbour(%d, %d) = %d\n", x, y, res); return res; } int next_x(int x) { x++; if (x == n) { return 0; } return x; } int next_y(int x, int y) { if (x == n - 1) { return y + 1; } return y; } int prev_x(int x, int y) { if (x == 0) { return 0; } return x - 1; } int prev_y(int x, int y) { if (y == 0) { return 0; } return y - 1; } void possible(int x, int y, int K, std::vector<int> v) { //printf("possible(%d, %d, %d)\n", x, y, K); if (K == 0) { std::sort(v.begin(), v.end()); results.insert(v); return; } if (y == n) { return; } for (int c = x; c < n; c++) { //printf("I: %d %d %d\n", c, y, K); if (!t[c][y] && has_neighbour(c, y)) { t[c][y] = true; std::vector<int> copy = std::vector<int>(v); copy.push_back(c + y * n); possible(prev_x(c, y), prev_y(c, y), K - 1, copy); t[c][y] = false; } } for (int r = y + 1; r < n; r++) { for (int c = 0; c < n; c++) { //printf("II: %d %d %d\n", c, r, K); //printf("%d %d\n", t[c][r], has_neighbour(c, r)); if (!t[c][r] && has_neighbour(c, r)) { t[c][r] = true; std::vector<int> copy = std::vector<int>(v); copy.push_back(c + r * n); possible(prev_x(c, r), prev_y(c, r), K - 1, copy); t[c][r] = false; } } } } void print_results() { for (std::set<std::vector<int> >::iterator it = results.begin(); it != results.end(); it++) { std::vector<int> v = *it; for (std::vector<int>::iterator it2 = v.begin(); it2 != v.end(); it2++) { printf("%2d ", *it2); } printf("\n"); } } void brute() { possible(0, 0, k, std::vector<int>()); //print_results(); printf("%d\n", (int)results.size()); } int main(int argc, char ** argv) { input(); brute(); return 0; }
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 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | #include<cstdio> #include<vector> #include<set> #include<algorithm> int n,k; bool ** t; std::set<std::vector<int> > results; void print_array() { for (int r = 0; r < n; r ++) { for (int c = 0; c < n; c++) { printf("%d", t[c][r]); } printf("\n"); } } void input() { scanf("%d %d", &n, &k); t = new bool * [n]; for (int i = 0; i < n; i++) { t[i] = new bool[n]; } char * q = new char[n]; for (int r = 0; r < n; r++) { scanf("%s", q); for (int c = 0; c < n; c++) { t[c][r] = (q[c] == '#'); } } //print_array(); } bool get_if_in_range(int x, int y) { // true = occupied if (x >= 0 && x < n && y >= 0 && y < n) { return t[x][y]; } return false; } bool has_neighbour(int x, int y) { //print_array(); bool res = get_if_in_range(x - 1, y) || get_if_in_range(x, y - 1) || get_if_in_range(x + 1, y) || get_if_in_range(x, y + 1); //printf("has_neighbour(%d, %d) = %d\n", x, y, res); return res; } int next_x(int x) { x++; if (x == n) { return 0; } return x; } int next_y(int x, int y) { if (x == n - 1) { return y + 1; } return y; } int prev_x(int x, int y) { if (x == 0) { return 0; } return x - 1; } int prev_y(int x, int y) { if (y == 0) { return 0; } return y - 1; } void possible(int x, int y, int K, std::vector<int> v) { //printf("possible(%d, %d, %d)\n", x, y, K); if (K == 0) { std::sort(v.begin(), v.end()); results.insert(v); return; } if (y == n) { return; } for (int c = x; c < n; c++) { //printf("I: %d %d %d\n", c, y, K); if (!t[c][y] && has_neighbour(c, y)) { t[c][y] = true; std::vector<int> copy = std::vector<int>(v); copy.push_back(c + y * n); possible(prev_x(c, y), prev_y(c, y), K - 1, copy); t[c][y] = false; } } for (int r = y + 1; r < n; r++) { for (int c = 0; c < n; c++) { //printf("II: %d %d %d\n", c, r, K); //printf("%d %d\n", t[c][r], has_neighbour(c, r)); if (!t[c][r] && has_neighbour(c, r)) { t[c][r] = true; std::vector<int> copy = std::vector<int>(v); copy.push_back(c + r * n); possible(prev_x(c, r), prev_y(c, r), K - 1, copy); t[c][r] = false; } } } } void print_results() { for (std::set<std::vector<int> >::iterator it = results.begin(); it != results.end(); it++) { std::vector<int> v = *it; for (std::vector<int>::iterator it2 = v.begin(); it2 != v.end(); it2++) { printf("%2d ", *it2); } printf("\n"); } } void brute() { possible(0, 0, k, std::vector<int>()); //print_results(); printf("%d\n", (int)results.size()); } int main(int argc, char ** argv) { input(); brute(); return 0; } |