HDU1045Fire Net
题目大意：在图上放置炮台，并且炮台之间不能相互威胁（即两个炮台不能中间无阻碍地放置在同行或同列），个人感觉有点像N皇后的问题，只不过进阶的东西就是多了墙
解题思路：做这题时想起了当时做N皇后的解法，只不过多了一步遇到墙壁就停止，不过发现在你不放在这个位置时，准备回溯你要把之前标记的行和列全部清空，问题就来了，如果你在清空标记时遇到有一格同时被两个炮台标记怎么办，这时就换种思路，即你每当要放炮台时沿着四个方向找有没有炮台，有就不能放，没有就放；其实上面那个做法可以用一个二层数组标记，只不过可能会比较麻烦
15ms代码如下，可能还可以优化，暂时没想到：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
char map[10][10];
int book[10][10],n,m,MAX,xia[4][2]={0,1,1,0,0,-1,-1,0};
bool pan(int x,int y) //判断坐标是否遇到墙壁或者越界
{
if(map[x][y]=='X' || x<0|| x>=n || y<0 || y>=m)
return false;
return true;
}
bool cr(int i,int x,int y) //沿着第i个方向一直查询如果遇到炮台返回真否则假即该方向符合条件
{
if(pan(x,y))
{
if(!book[x][y])
return cr(i,x+xia[i][0],y+xia[i][1]);
else
return true;
}
return false;
}
bool find(int x,int y) //查询四个方向
{
if(cr(0,x,y)||cr(1,x,y)||cr(2,x,y)||cr(3,x,y))
return false;
return true;
}
void dfs(int k)
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(pan(i,j) && find(i,j) && !book[i][j]) //该节点四个方向无障碍 并且没被放过
{
if(k+1>MAX) //更新数据（为什么不能是直接最大值+1呢？因为该位置存在着放和不放 有点像01背包，要整体最优）
MAX=k+1;
book[i][j]=1;
dfs(k+1);
book[i][j]=0; //回溯
}
}
return ;
}
int main()
{
int i,j;
while(~scanf("%d",&n) && n)
{
m=n;
MAX=0;
getchar();
for(i=0;i<n;i++)
scanf("%s",map[i]);
memset(book,0,sizeof(book));
dfs(0);
printf("%d\n",MAX);
}
return 0;
}
查看18道真题和解析