ZOJ 1002 Fire Net

//类似八皇后问题，只需要用DFS回溯即可,注意要一行一行一列一列地扫，不能直接用4个方向的DFS遍历
#include <stdio.h>
int N;
int cal, max;
char map[10][10];
int canput( int x, int y );
void dfs( int cal );
int main()
{while ( scanf( "%d", &N ) && N ){int i, j;getchar();cal = 0;max = -10;for( i = 1; i <= N; i++ ){for( j = 1; j <= N; j++ )scanf( "%c", &map[i][j] );getchar();}dfs( cal );printf( "%d\n", max );}return 0;
}
void dfs( int cal )
{int i, j;if( cal > max )max = cal;for(  i = 1; i <= N; i++ )for(  j = 1; j <= N; j++ )if( map[i][j] == '.' && canput(i,j) ){map[i][j] = 'b';dfs( cal+1 );map[i][j] = '.';}
}
int canput( int x, int y )
{int i;for(  i = x; i > 0; i-- ){if( map[i][y] == 'b' )return 0;if( map[i][y] == 'X' )break;}for( i = x; i <= N; i++ ){if( map[i][y] == 'b' )return 0;if( map[i][y] == 'X' )break;}for( i = y; i > 0; i-- ){if( map[x][i] == 'b' )return 0;if( map[x][i] == 'X' )break;}for( i = y; i <= N; i++ ){if( map[x][i] == 'b' )return 0;if( map[x][i] == 'X' )break;}return 1;
}