浙大acm题库1002求助浙大acm题库,题号1002,那个有关设置火力点最大数量的题目,小弟写的算法在其上编译器运行,得到的回应是超时.费尽脑汁也想不出好的算法了,只好来这里求助个位大侠,恳请指点一二,感激不尽!深度遍历?怎么能联系上呢?能说得详细些么?我的代码本来是用队列控制的,为了省时间,改成数组了,也不行能说一下思路么?然后我想自己写,代码贴补不上了,有字数限制
网友回答
是FireNet那个题么?
典型的DFS
这个是我的代码:
#include
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,r,stdin);
char map[5][5];
int i,n,firenet;
while(scanf(%d,&n)!=EOF && n){
firenet = 0;
for(i = 0; i dfs(map,n,0,0,firenet);
printf(%d\n,firenet);
}return 0;
}