这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门:
http://acm.hdu.edu.cn/showproblem.php?pid=1045
分析:
将一个NN的方块依次编号0...NN-1。 可以从0到N*N-1一直判定,假设当前点可以放大炮,则放上,并继续搜索,然后回溯。
AC代码:
#include
using namespace std;
char map[4][4];
int _max;
int n;
bool fun(int x, int y)
{
// 横向
for(int i=y-1; i>=0; --i)
{
if(map[x][i] == '@')
return 0;
if(map[x][i] == 'X')
break;
}
// 竖向
for(int i=x-1; i>=0; --i)
{
if(map[i][y] == '@')
return 0;
if(map[i][y] == 'X')
break;
}
return 1;
}
int solve(int k, int cnt)
{
int x, y;
if(k == n*n)
{
if(_max < cnt)
{
_max = cnt;
return 0;
}
}
else
{
x = k/n;
y = k%n;
if(map[x][y] == '.' && fun(x, y))
{
map[x][y] = '@';
solve(k+1, cnt+1);
map[x][y] = '.';
}
solve(k+1, cnt);
}
}
int main()
{
//freopen("input.txt", "r", stdin);
while(cin >> n && n)
{
_max = 0;
for(int i=0; i> map[i][j];
solve(0, 0);
cout << _max << endl;
}
return 0;
}