浙大acm题库1002求助

来源：百度知道 编辑：UC知道 时间：2024/06/30 09:41:35
浙大acm题库，题号1002，那个有关设置火力点最大数量的题目，小弟写的算法在其上编译器运行，得到的回应是超时。费尽脑汁也想不出好的算法了，只好来这里求助个位大侠，恳请指点一二，感激不尽！
深度遍历？怎么能联系上呢？能说得详细些么？
我的代码本来是用队列控制的，为了省时间，改成数组了，也不行
能说一下思路么？然后我想自己写，谢谢了！
代码贴补不上了，有字数限制

是FireNet那个题么?
典型的DFS
这个是我的代码:

#include <iostream>
using namespace std;

bool canput(char map[5][5], int y, int x){
if(map[y][x] != '.')return 0;
int i;
for(i = y - 1; i >= 0; i--){
if(map[i][x] == 'X')break;
if(map[i][x] == 'F')return 0;
}
for(i = x - 1; i >= 0; i--){
if(map[y][i] == 'X')break;
if(map[y][i] == 'F')return 0;
}
return 1;
}

void dfs(char map[5][5], int n, int depth, int put, int &max){
if(put > max)max = put;

if(depth >= n*n)
return;

dfs(map,n,depth+1,put,max);

int y = depth / n, x = depth % n;

if(canput(map,y,x)){
map[y][x] = 'F';
put++;
dfs(map, n, depth+1, put, max);
map[y][x] = '.';
put--;
}
}

int main(){
//freopen("input.txt&q