题意:给你一个地图,然后地图上会放置一些炮台,这些炮台会往四个方向发射无穷远,保证多个炮台之间不能被打到,求最大放置的炮台数。

其实就是类似于炸弹人游戏一样,不过这里是射程无穷远而已。DFS题,注意数组状态保存以及方向变化。


题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1045


代码:

Memory: 1804 KB
Time: 15 MS
Language: C++
Result: Accepted
#include <iostream>
#include <memory.h>
#include <cstdio>
using namespace std;
#define MAX 4
char omap[MAX][MAX];
int flag[MAX][MAX];
int n, ans;
int go[4][2]={1,0,-1,0,0,1,0,-1};
bool chkb(int x, int y){    ///检查边界
    if(x<0 || y<0 || x>=n || y>=n)return 0;
    return 1;
}
bool chkg(int x, int y){    ///检查是否可走
    if(flag[x][y] || omap[x][y]=='X')return 0;
    return 1;
}
void dfs(int x, int y, int v){
    if(!chkg(x, y))return;
    int dx, dy;
    int temp[MAX][MAX];
    memcpy(temp, flag, sizeof(temp));
    flag[x][y] = 1;
    v++;
    for(int i=0;i<4;i++){
        for(dx=x+go[i][0],dy=y+go[i][1];chkb(dx, dy) && omap[dx][dy]!='X';dx+=go[i][0],dy+=go[i][1])flag[dx][dy]=1;
    }
    if(v>ans)ans=v;
    for(int i=x*n+y+1;i<n*n;i++)dfs(i/n, i%n, v);
    memcpy(flag, temp, sizeof(flag));
}
int main()
{
    //freopen("in.txt", "r", stdin);
    while(cin>>n && n){
        ans = 0;
        memset(flag, 0, sizeof(flag));
        for(int i=0;i<n;i++)scanf("%s", &omap[i]);
        for(int i=0;i<n*n;i++)dfs(i/n, i%n, 0);
        cout<<ans<<endl;
    }
    return 0;
}