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 #include using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define INT(x) int x; scanf("%d", &x) const int DX[4] = {0, 1, 0, -1}, DY[4] = {1, 0, -1, 0}; int n, k; char a[3000][3001]; int connect[3000][3000]; int cx[3000], cy[3000]; int numcon; int res; void go(int s) { if (!k) { ++res; if (res == 1000000007) res = 0; return; } int nn = numcon; FOR(i,s,nn) { int x = cx[i], y = cy[i]; a[x][y] = '*'; REP(kk,4) { int xx = x + DX[kk]; int yy = y + DY[kk]; if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] == '.' && ++connect[xx][yy] == 1) { cx[numcon] = xx; cy[numcon] = yy; ++numcon; } } --k; go(i + 1); ++k; REP(kk,4) { int xx = x + DX[kk]; int yy = y + DY[kk]; if (xx >= 0 && xx < n && yy >= 0 && yy < n && a[xx][yy] == '.' && !--connect[xx][yy]) --numcon; } a[x][y] = '.'; } } int main() { INT(n1); INT(k1); n = n1; k = k1; REP(i,n) scanf("%s", &a[i]); REP(i,n) REP(j,n) if (a[i][j] == '#') REP(kk,4) { int ii = i + DX[kk]; int jj = j + DY[kk]; if (ii >= 0 && ii < n && jj >= 0 && jj < n && a[ii][jj] == '.' && ++connect[ii][jj] == 1) { cx[numcon] = ii; cy[numcon] = jj; ++numcon; } } go(0); printf("%d\n", res); }