好久都沒(méi)有寫(xiě)解題總結(jié)了，手生了。抓緊時(shí)間做題，不然等到開(kāi)學(xué)了，就不能這么爽的做題了。
這個(gè)題數(shù)據(jù)量不大，可以用回溯。剛開(kāi)始做的時(shí)候，是用廣搜，但是寫(xiě)起來(lái)超麻煩，代碼量極大，很容易出錯(cuò)。參考了大牛們的做法，才想起來(lái)和N皇后問(wèn)題很像。我們可以從一個(gè)點(diǎn)出發(fā)，然后往右下擴(kuò)散，擴(kuò)散完了之后，再回溯，再擴(kuò)散…… 問(wè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 ) ){
// 回溯標(biāo)記
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開(kāi)始回溯
trace( 0, 0, 0 ) ;
cout << maxi << endl ;
}
return 0 ;
}