#include <iostream> using namespace std; string sa; int n,k; long long res=0; bool tab[3001][3001]; bool kolor[3001][3001]; bool visit[3001][3001]; int wx[10]; int wy[10]; bool dfs(int x, int y){ visit[x][y] = 1; bool res = 0; if(tab[x+1][y]) res = 1; if(tab[x-1][y]) res = 1; if(tab[x][y+1]) res = 1; if(tab[x][y-1]) res = 1; if(kolor[x+1][y] && !visit[x+1][y]) res = res | dfs(x+1,y); if(kolor[x-1][y] && !visit[x-1][y]) res = res | dfs(x-1,y); if(kolor[x][y+1] && !visit[x][y+1]) res = res | dfs(x,y+1); if(kolor[x][y-1] && !visit[x][y-1]) res = res | dfs(x,y-1); return res; } void check(){ bool flag = 1; for(int i=1;i<=k;i++){ if( !visit[wx[i]][wy[i]] ){ flag = flag & dfs( wx[i],wy[i] ); } } for(int i=1;i<=k;i++){ visit[wx[i]][wy[i]] = 0; } if(flag){ //for(int i=1;i<=k;i++){ // cout<<wx[i]<<" "<<wy[i]<<endl; //}cout<<endl; res++; } } int select(int p, int lx, int ly){ if( p > k ){ check(); return 0; } for( int j = ly+1; j <= n; j++ ){ if( !tab[lx][j] ){ kolor[lx][j] = 1; wx[p] = lx; wy[p] = j; select(p+1,lx,j); kolor[lx][j] = 0; } } for( int i = lx+1; i <= n; i++ ){ for( int j = 1; j <= n; j++ ){ if( !tab[i][j] ){ kolor[i][j] = 1; wx[p] = i; wy[p] = j; select(p+1,i,j); kolor[i][j] = 0; } } } return 0; } int main(){ ios_base::sync_with_stdio(false); cin>>n>>k; for(int i=1;i<=n;i++){ cin>>sa; for(int j=1;j<=n;j++){ if( sa[j-1] == '#' ){ tab[i][j] = 1; } } } select(1,1,0); cout<<res % 1000000007 <<endl; }
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 | #include <iostream> using namespace std; string sa; int n,k; long long res=0; bool tab[3001][3001]; bool kolor[3001][3001]; bool visit[3001][3001]; int wx[10]; int wy[10]; bool dfs(int x, int y){ visit[x][y] = 1; bool res = 0; if(tab[x+1][y]) res = 1; if(tab[x-1][y]) res = 1; if(tab[x][y+1]) res = 1; if(tab[x][y-1]) res = 1; if(kolor[x+1][y] && !visit[x+1][y]) res = res | dfs(x+1,y); if(kolor[x-1][y] && !visit[x-1][y]) res = res | dfs(x-1,y); if(kolor[x][y+1] && !visit[x][y+1]) res = res | dfs(x,y+1); if(kolor[x][y-1] && !visit[x][y-1]) res = res | dfs(x,y-1); return res; } void check(){ bool flag = 1; for(int i=1;i<=k;i++){ if( !visit[wx[i]][wy[i]] ){ flag = flag & dfs( wx[i],wy[i] ); } } for(int i=1;i<=k;i++){ visit[wx[i]][wy[i]] = 0; } if(flag){ //for(int i=1;i<=k;i++){ // cout<<wx[i]<<" "<<wy[i]<<endl; //}cout<<endl; res++; } } int select(int p, int lx, int ly){ if( p > k ){ check(); return 0; } for( int j = ly+1; j <= n; j++ ){ if( !tab[lx][j] ){ kolor[lx][j] = 1; wx[p] = lx; wy[p] = j; select(p+1,lx,j); kolor[lx][j] = 0; } } for( int i = lx+1; i <= n; i++ ){ for( int j = 1; j <= n; j++ ){ if( !tab[i][j] ){ kolor[i][j] = 1; wx[p] = i; wy[p] = j; select(p+1,i,j); kolor[i][j] = 0; } } } return 0; } int main(){ ios_base::sync_with_stdio(false); cin>>n>>k; for(int i=1;i<=n;i++){ cin>>sa; for(int j=1;j<=n;j++){ if( sa[j-1] == '#' ){ tab[i][j] = 1; } } } select(1,1,0); cout<<res % 1000000007 <<endl; } |