回溯
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> using namespace std ; const int maxn = 9 ; char map[maxn][maxn] , vis[maxn] ; int ans , n , k , cnt ; void init() { memset( vis , 0 , sizeof( vis ) ) ; memset( map , 0 , sizeof( map ) ) ; ans = 0 ; cnt = 0 ; return ; } void input() { for( int i = 0 ; i < n ; ++i ) cin >> map[i] ; } bool is_ok( int x , int y ) { if( map[x][y] == '.'|| map[x][y] == '*' ) return false ; for( int i = x-1 ; i >= 0 ; --i ) if( map[i][y] == '*' ) return false ; for( int i = y-1 ; i >= 0 ; --i ) if( map[x][i] == '*' ) return false ; return true ; } void dfs( int x ) { if( cnt == k ) { ans++ ; return ; } if( x >= n ) { return ; } for( int i = 0 ; i < n ; ++i ) if( !vis[i] && map[x][i] == '#' ) { vis[i] = 1 ; cnt++ ; dfs( x+1 ) ; vis[i] = 0 ; cnt-- ; } dfs( x+1 ) ; } //void dfs( int x , int y ) //{ // if( cnt == k ) // { // ans++ ; // } // // if( x >= n-1 ) // return ; // // if( is_ok( x , y ) ) // { // map[x][y] = '*' ; // cnt++ ; // if( y >= n-1 ) // dfs( x+1 , 0 ) ; // else dfs( x , y+1 ) ; // map[x][y] = '#' ; // cnt-- ; // } // if( y >= n-1 ) // dfs( x+1 , y ) ; // else // dfs( x , y+1 ) ; // return ; //} void solve() { dfs( 0 ) ; } void output() { cout << ans << endl ; return ; } int main() { while( cin >> n >> k && ( n ^ -1 ) ) { init() ; input() ; solve() ; output() ; } return 0 ; }
