hdu 1045 Fire Net（回溯搜索）

搜索，回溯！！！人的一生避免不了會犯一些小錯誤！！！

那麼犯錯錯誤可以回頭的！不可以一直錯下去的！！！

#include<stdio.h>

#include<string.h>

int visit[10][10];
char map[10][10];
int n,ans,ss,t;

int judge(int x,int y)
{
int k;
if(x<0||x>=n||y<0||y>=n)
return 0;
if(visit[x][y]==1||map[x][y]=='X')
return 0;
for(k=x-1;k>=0;k--)
{
if(map[k][y]=='X')//判斷這一行中間是否有X
break;
if(visit[k][y]==1)
{
return 0;
}
}
for(k=y-1;k>=0;k--)
{
if(map[x][k]=='X')//判斷這一列中間是否有X
break;
if(visit[x][k]==1)
return 0;
}
return 1;//嚴格的篩選！
}

void dfs(int ss)
{
int x,y;
if(ss==n*n)
{
if(ans<t)
ans=t;
return ;
}
x=ss/n;y=ss%n;
if(judge(x,y))
{
t++;
visit[x][y]=1;
dfs(ss+1);
t--;
visit[x][y]=0;
dfs(ss+1);
}
else
dfs(ss+1);
}

int main()
{
int i;
while(scanf("%d",&n),n)
{
t=0;
for(i=0;i<n;i++)
scanf("%s",map[i]);
memset(visit,0,sizeof(visit));
ans=0;
dfs(0);
printf("%d\n",ans);
}
return 0;
}