ウバ639

つは8皇后の回想問題に類似します.最初はよく分かりませんでした.直接暴力を準備したらTLEができます.書きませんでした
他の人のコードを参考にしましたが、八皇后は一行ごとに記入します.この問題は壁があるので、同じ行に置いてもいいです.左から右に順番に置くべきです.
タイトル:http://uva.onlinejudge.org/index.php?option=com_オンラインjudge&Itemid=8&page=show_problem&problem=580
ACコード:

#include<stdio.h>
#define MAX 8
char map[MAX][MAX],n;
int vis[MAX][MAX];            //      ，           ，      
int ok_place(int i,int j){
	int left,up;
	for(left=j-1;left>=0;left--){
		if(vis[i][left]==-1)     
			break;         //    ，   
		if(vis[i][left]==0)  //  
			return 0;
	}
	for(up=i-1;up>=0;up--){
		if(vis[up][j]==-1)
			break;           //    
		if(vis[up][j]==0)
			return 0;        //    
	}
	return 1;
}
int dfs(int i,int j,int m){               //i ，j 
	int count=0,max=0;
	while(i<m){
		if(vis[i][j]&&(vis[i][j]!=-1)&&ok_place(i,j)){
			vis[i][j]=0;          //       
			count=dfs(i,j+1,m)+1;
			if(max<count)
				max=count;
			vis[i][j]=1;          //          
		}
		if(j>=m-1){                //           ，                      
			i++;                   //            
			j=0;
		}
		else
			j++;
	}
	return max;
}
int main()
{
	int i,j,maxsum;
	while(scanf("%d",&n)!=EOF&&n){
		for(i=0;i<n;i++){
			scanf("%s",map[i]);
			for(j=0;j<n;j++){
				if(map[i][j]=='X')
					vis[i][j]=-1;         //-1    
				else
					vis[i][j]=1;          //1       
			}
		}
		maxsum=0;
		maxsum=dfs(0,0,n);
		printf("%d
",maxsum);
	}
	return 0;
}