#include <cstdio> #include <queue> #include <map> #include <algorithm> #include <vector> using namespace std; const int N = 100; const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}; bool board[N + 1][N + 1]; map<vector<pair<int, int> >, bool> M; int n, k, result; pair<int, int> start; void read() { scanf("%d%d", &n, &k); for(int i = 0; i < n; ++i) { getchar(); for(int j = 0; j < n; ++j) { char a; scanf("%c", &a); if(a == '#') { board[i][j] = true; start = make_pair(i, j); } } } } void go(int howMany, vector<pair<int, int> > V) { sort(V.begin(), V.end()); if(M.find(V) != M.end()) { return; } M[V] = true; if(howMany == k) { ++result; return; } bool odw[N + 1][N + 1]; for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { odw[i][j] = false; } } queue<pair<int, int> > Q; vector<pair<int, int> > temp; odw[start.first][start.second] = true; Q.push(start); while(!Q.empty()) { pair<int, int> v = Q.front(); Q.pop(); for(int i = 0; i < 4; ++i) { int nx = v.first + dx[i], ny = v.second + dy[i]; if(nx == -1 or nx == n or ny == -1 or ny == n or odw[nx][ny]) continue; if(!board[nx][ny]) { board[nx][ny] = true; temp = V; temp.push_back(make_pair(nx, ny)); go(howMany + 1, temp); board[nx][ny] = false; } else Q.push(make_pair(nx, ny)); odw[nx][ny] = true; } } } int main() { read(); vector<pair<int, int> > V; go(0, V); printf("%d", result); 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 | #include <cstdio> #include <queue> #include <map> #include <algorithm> #include <vector> using namespace std; const int N = 100; const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}; bool board[N + 1][N + 1]; map<vector<pair<int, int> >, bool> M; int n, k, result; pair<int, int> start; void read() { scanf("%d%d", &n, &k); for(int i = 0; i < n; ++i) { getchar(); for(int j = 0; j < n; ++j) { char a; scanf("%c", &a); if(a == '#') { board[i][j] = true; start = make_pair(i, j); } } } } void go(int howMany, vector<pair<int, int> > V) { sort(V.begin(), V.end()); if(M.find(V) != M.end()) { return; } M[V] = true; if(howMany == k) { ++result; return; } bool odw[N + 1][N + 1]; for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { odw[i][j] = false; } } queue<pair<int, int> > Q; vector<pair<int, int> > temp; odw[start.first][start.second] = true; Q.push(start); while(!Q.empty()) { pair<int, int> v = Q.front(); Q.pop(); for(int i = 0; i < 4; ++i) { int nx = v.first + dx[i], ny = v.second + dy[i]; if(nx == -1 or nx == n or ny == -1 or ny == n or odw[nx][ny]) continue; if(!board[nx][ny]) { board[nx][ny] = true; temp = V; temp.push_back(make_pair(nx, ny)); go(howMany + 1, temp); board[nx][ny] = false; } else Q.push(make_pair(nx, ny)); odw[nx][ny] = true; } } } int main() { read(); vector<pair<int, int> > V; go(0, V); printf("%d", result); return 0; } |