sunkehappy

        好久都沒有寫解題總結了，手生了。抓緊時間做題，不然等到開學了，就不能這么爽的做題了。

        這個題數據量不大，可以用回溯。剛開始做的時候，是用廣搜，但是寫起來超麻煩，代碼量極大，很容易出錯。參考了大牛們的做法，才想起來和N皇后問題很像。我們可以從一個點出發，然后往右下擴散，擴散完了之后，再回溯，再擴散…… 問題解決。

#include<iostream>
#define DEBUG 0
using namespace std ;

int n, maxi ;
char a[5][5] ;

bool legal( int x, int y )
{
    int i, j ;
    for( i=x-1; i>=0; --i ){
        if( a[i][y] == '@' )
            return false ;
        else if( a[i][y] == 'X' )
            break ;
    }
    for( j=y-1; j>=0; --j ){
        if( a[x][j] == '@' )
            return false ;
        else if( a[x][j] == 'X' )
            break ;
    }
    return true ;
}

void trace( int x, int y, int geshu )
{
    if( x == n )
        maxi = maxi>geshu ? maxi:geshu ;
    else{
        if( y == n )
            trace( x+1, 0, geshu ) ;
        else {
            if( a[x][y]=='.' && legal( x, y ) ){
                // 回溯標記 
                a[x][y] = '@' ;
                trace( x, y+1, geshu+1 ) ;
                a[x][y] = '.' ;
            }
            trace( x, y+1, geshu ) ;
        }
    }
}

int main()
{
    #if DEBUG
    freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
    freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
    #endif

    int i, j ;
    while( cin >> n ){
        if( !n )
            break ;
        for( i=0; i<n; ++i ){
            for( j=0; j<n; ++j ){
                cin >> a[i][j] ;
            }
        }
        maxi = 0 ;
        // 從0，0開始回溯 
        trace( 0, 0, 0 ) ;
        cout << maxi << endl ;
    }
    
    return 0 ;
}