Fire Net(深搜 和一前不一样的深搜)
Fire Net(深搜 和一前不一样的深搜)
1944864971 发表于2年前
Fire Net(深搜 和一前不一样的深搜)
  • 发表于 2年前
  • 阅读 3
  • 收藏 0
  • 点赞 0
  • 评论 0

新睿云服务器60天免费使用,快来体验!>>>   

/*
http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1162

本题妙处:
用一个数对行取商是行的坐标 对行取余是列的坐标;
注意: 二位数组必须从[0][0]开始,并且这个数也是从零开始的;

以前做的题目都是在for循环里面进行递归

*/

include

include

include

include

include

include

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;
}

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 57
码字总数 0
×
1944864971
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: