现在的位置: 首页 > 综合 > 正文

hdu(1045)Fire Net(深搜+回朔)

2013年08月26日 ⁄ 综合 ⁄ 共 786字 ⁄ 字号 评论关闭

 

#include"stdio.h"
#include"string.h"
char map[20][20];
int n,cnt;
int judge(int x,int y)//判段此位置是否可以放。。
{
 int i;
 if(map[x][y]=='X')
  return 0;
 for(i=x-1;i>=0;i--)
 {
  if(map[i][y]=='@')//说明已经放过。
   return 0;
  if(map[i][y]=='X')
   break;
 }
 for(i=y-1;i>=0;i--)
 {
  if(map[x][i]=='@')
   return 0;
  if(map[x][i]=='X')
   break;
 }
 return 1;
}
void dfs(int k,int count)//k表示第几个点,count表示到这个点最多可以放的个数。
{

 if(k==n*n)//这里不是n*n-1,因为第n*n-1个点,仍有两种选择,放与不放。。到达了节点n*n。。
 {
    if(count>cnt)
    {
    cnt=count;
  return ;
    }
 }
 else
 {
  int x,y;//求出此点的坐标。
  x=k/n;
  y=k%n;
  if(judge(x,y))//如果可以放就放,放完之后还要搜索不放的情况,最后再去能放最多的个数。。
  {
   map[x][y]='@';
   dfs(k+1,count+1);
   map[x][y]='.';
  }
  dfs(k+1,count);
 }

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

抱歉!评论已关闭.