HDU 1045 Fire Net(DFS回溯)
http://acm.hdu.edu.cn/showproblem.php?pid=1045
题意:给你一个N*N的棋盘,棋盘中有空白格和墙’X’,现在要你在空白格上放大炮,要求任意两个大炮不能在同行或者同列,除非他们之间有一个’X’墙.问你最多能放几门大炮.
分析:本问题与8皇后问题有一点点类似.
八皇后问题是对于每行的情况看放哪个位置,但是这里的情况有点特殊.我们需要看对于每个格子放还是不放.
如果我们单纯的用DFS对每个空格做两种选择(放或不放),那么明显这么做我们可能超时.
对于这种情况,我们应该给所有放大炮的格子定序.即我们假设我们是从上到下,从左到右来放大炮的.所以我们首先枚举第一个大炮应该放的位置,确定了首位后,我们在从该位置之后的所有位置中选出第二个应该放大炮的位置….直到我们到达右下角.(定序)
想想其实单纯的10考虑放与不放问题,需要考虑的分支数目好像与上面定序的情况类似,都是2^n种情况.但是到底哪种方式更快我还是有疑问.下面分别实现了两种方式的代码.事实说明,其实两种方式实现的效果几乎是一样的.
AC代码:定序DFS回溯, 15ms,224K memory
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=10;
int dr[]={-1,1,0,0};
int dc[]={0,0,-1,1};
char map[maxn][maxn];
int vis[maxn][maxn];
int n;
int ans;//解
void dfs(int pos,int num)//pos是当前位置,num是之前已经放了几个大炮
{
int r=pos/n, c=pos%n;
if(map[r][c]=='X') return;
if(vis[r][c]==1) return;
int pre_vis[maxn][maxn];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
pre_vis[i][j]=vis[i][j];//保存下当前的状态,用于回溯
vis[r][c]=1;
ans = max(ans,num+1);
for(int d=0;d<4;d++)//从当前方向往4个方向走,遇到墙就停下来
{
int nr=r, nc=c;
while(1)
{
nr=nr+dr[d], nc=nc+dc[d];
if(nr<0||nr>=n||nc<0||nc>=n||map[nr][nc]=='X') break;
vis[nr][nc]=1;
}
}
for(int i=pos+1;i<n*n;i++) //定序,选取下一个位置放大炮
dfs(i,num+1);
for(int i=0;i<n;i++)//回溯
for(int j=0;j<n;j++)
vis[i][j]=pre_vis[i][j];
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
ans=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
scanf("%s",map[i]);
for(int i=0;i<n*n;i++) dfs(i,0);
printf("%d\n",ans);
}
}
AC代码:单纯10考虑每个格子放还是不放. 0ms,224Kmemory
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=10;
int dr[]={-1,1,0,0};
int dc[]={0,0,-1,1};
char map[maxn][maxn];
int vis[maxn][maxn];
int n;
int ans;//解
void dfs(int pos,int num)//pos是当前位置,num是之前已经放了几个大炮
{
if(pos==n*n) return ; //不加这句就会出现越界错误
dfs(pos+1,num);
int r=pos/n, c=pos%n;
if(map[r][c]=='X') return;
if(vis[r][c]==1) return;
int pre_vis[maxn][maxn];
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
pre_vis[i][j]=vis[i][j];//保存下当前的状态,用于回溯
vis[r][c]=1;
ans = max(ans,num+1);
for(int d=0;d<4;d++)//从当前方向往4个方向走,遇到墙就停下来
{
int nr=r, nc=c;
while(1)
{
nr=nr+dr[d], nc=nc+dc[d];
if(nr<0||nr>=n||nc<0||nc>=n||map[nr][nc]=='X') break;
vis[nr][nc]=1;
}
}
//for(int i=pos+1;i<n*n;i++) //定序,选取下一个位置放大炮
dfs(pos+1,num+1); //直接考虑相邻的下一个格子
for(int i=0;i<n;i++)//回溯
for(int j=0;j<n;j++)
vis[i][j]=pre_vis[i][j];
}
int main()
{
while(scanf("%d",&n)==1&&n)
{
ans=0;
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
scanf("%s",map[i]);
dfs(0,0);
printf("%d\n",ans);
}
}
分享到:
相关推荐
搜索 dfs 解题代码 hdu1241
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码