include

using namespace std;
char diaoBao[5][5];
int m,min1=0;
bool isFang(int x,int y)
{
for(int i=x-1; i>=0; i--)
{
if(diaoBao[i][y]=='0')//此点是否和以前放置的点冲突，0代表此行和它离的最近的点已经放置过直接返回假值
return false;
if(diaoBao[i][y]=='X')//遇到墙了，说明此行可以放置退出看看列是否能放置
break;
}
for(int i=y-1; i>=0; i--)// 列
{
if(diaoBao[x][i]=='0')
return false;
if(diaoBao[x][i]=='X')
break;
}
return true;
}
void dfs(int cur,int s)
{
if(cur==m*m)
{
if(s>min1)
min1=s;
return;
}
int x=cur/m;//行的坐标
int y=cur%m;//列的坐标

if(diaoBao[x][y]=='.'&&isFang(x,y))//满足条件能够放置
{
    diaoBao[x][y]='0';
    dfs(cur+1,s+1);//能够放置的条件下  s+1
    diaoBao[x][y]='.';
}
dfs(cur+1,s);//注意：  前面不能加 else  不满足条件的情况下s不再加1   但是在满足条件下上一步已经执行了，这一步只是起到
                 //向下一步继续扩展不影响s的值

}
int main()
{
while(scanf("%d",&m),m)
{
min1=0;
memset(diaoBao,'.',sizeof(diaoBao));
for(int i=0; i<m; i++)
scanf("%s",diaoBao[i]);
dfs(0,0);
printf("%d\n",min1);
}
return 0;
}

巴特西

Fire Net（深搜和一前不一样的深搜）

include

include

include

include

include

include

include

最新文章

热门文章

巴特西

Fire Net（深搜 和一前不一样的深搜）

include

include

include

include

include

include

include

最新文章

热门文章

Fire Net（深搜和一前不一样的深搜）