随笔 - 19, 文章 - 0, 评论 - 2, 引用 - 0
数据加载中……

zoj1002 Fire Net

        好久都没有写解题总结了,手生了。抓紧时间做题,不然等到开学了,就不能这么爽的做题了。

        这个题数据量不大,可以用回溯。刚开始做的时候,是用广搜,但是写起来超麻烦,代码量极大,很容易出错。参考了大牛们的做法,才想起来和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
+10, 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( 000 ) ;
        cout 
<< maxi << endl ;
    }

    
    
return 0 ;
}

posted on 2009-07-26 17:33 祝你好运! 阅读(204) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理