ZOJ 1002 Fire Net

ZOJ 1002 Fire Net

深搜题，和八皇后类似，每一个节点，有两个子节点，即放与不放 炮台。

#include <stdio.h>
#include <string.h>
#define MAXN (10+5)int N,amount,MAX;
char map[MAXN][MAXN],att[MAXN][MAXN];int max(int x,int y)
{return x>y? x:y;
}int isvalid( int cloumn,int row )
{int i;for( i= cloumn -1 ; i>=0 ;i-- ){if( att[i][row] == '@' ) return 0;if( att[i][row] == 'X' ) break;}for( i= row -1 ; i>=0 ;i-- ){if( att[cloumn][i] == '@' ) return 0;if( att[cloumn][i] == 'X' ) break;}return 1;
}void DFS(int cloumn,int row)
{int next_cloumn,next_row;if( cloumn == N) {	MAX=max(MAX,amount);return ;}if( row+1 == N ) {	next_cloumn = cloumn+1;	next_row = 0;}else {	next_cloumn = cloumn;	next_row = row+1;	}if( map[cloumn][row] == 'X' ){	att[cloumn][row] ='X'; DFS(next_cloumn,next_row);}else{if(  isvalid( cloumn, row ) ){att[cloumn][row] = '@';amount++;DFS(next_cloumn,next_row);amount--;}att[cloumn][row] = '.';DFS( next_cloumn, next_row );}
}int main()
{int i;while( scanf("%d",&N) && N!=0){MAX=0;  amount=0;memset( att,0,sizeof(att) );for(i=0;i<N;i++)scanf( "%s",map[i] );DFS(0,0);printf("%dn",MAX);}return 0;
}