好久都没有写解题总结了,手生了。抓紧时间做题,不然等到开学了,就不能这么爽的做题了。
这个题数据量不大,可以用回溯。刚开始做的时候,是用广搜,但是写起来超麻烦,代码量极大,很容易出错。参考了大牛们的做法,才想起来和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 ;
}
