51. N-Queens
----------------------------------------------------------------------------
Mean:
N-Queen问题.
analyse:
dfs基本功.
Time complexity: O(N)
view code
1.第一发超时了，回过头来看看自己像shi一样的代码也是醉了.
class Solution { public : vector < vector < string >> solveNQueens( int n) { __init(n); dfs( 0 ,n , mat , 0); return res; } void dfs( int num , int n , vector < string > & mat , int queen) { if( num ==n *n) { if( queen ==n) res . push_back( mat); return ; } int row = num /n; int col = num %n; if( check( mat , row , col ,n)) { mat [ row ][ col ] = 'Q'; dfs( num + 1 ,n , mat , queen + 1); mat [ row ][ col ] = '.'; } mat [ row ][ col ] = '.'; dfs( num + 1 ,n , mat , queen); } bool check( vector < string > & mat , int row , int col , int n) { for( int i = 0; i <n; ++ i) { if(( mat [ row ][ i ] == 'Q' && i != col) || ( mat [ i ][ col ] == 'Q' && i != row)) return false; } // left,up int x = row , y = col; while( x && y) -- x , -- y; while( x <n && y <n) { if( mat [ x ][ y ] == 'Q' && ( !( x == row && y == col))) return false; ++ x , ++ y; } // right,up x = row , y = col; while( x && ( y <n - 1)) -- x , ++ y; while( x <n && y) { if( mat [ x ][ y ] == 'Q' && ( !( x == row && y == col))) return false; ++ x , -- y; } return true; } void __init( int n) { res . clear(); mat =*( new vector < string >(n , string(n , '.'))); } private : vector < string > mat; vector < vector < string >> res; };
2.优化了dfs调用和check()函数，效率提升了一个档次.
class Solution { public : vector < vector < string >> solveNQueens( int n) { __init(n); dfs( 0 ,n , mat); return res; } void dfs( int row , int n , vector < string > & mat) { if( row ==n) { res . push_back( mat); return ; } for( int col = 0; col <n; ++ col) { if( check( mat , row , col ,n)) { mat [ row ][ col ] = 'Q'; dfs( row + 1 ,n , mat); mat [ row ][ col ] = '.'; } } } bool check( vector < string > & mat , int row , int col , int n) { // up for( int i = 0; i < row; ++ i) if( mat [ i ][ col ] == 'Q') return false; // left,up for( int i = row - 1 , j = col - 1; i >= 0 && j >= 0; -- i , -- j) if( mat [ i ][ j ] == 'Q') return false; // right,up for( int i = row - 1 , j = col + 1; i >= 0 && j <n; -- i , ++ j) if( mat [ i ][ j ] == 'Q') return false; return true; } void __init( int n) { res . clear(); mat =*( new vector < string >(n , string(n , '.'))); } private : vector < string > mat; vector < vector < string >> res; };