作业帮浙大acm题库1002求助浙大acm题库,题号1002,那个有关设置火力点最大数量的题目,小弟写的算法在其上编译器运行,得到的回应是超时.费尽脑汁也想不出好的算法了,只好来这里求助个位大侠,恳请
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/30 00:01:57
浙大acm题库1002求助浙大acm题库,题号1002,那个有关设置火力点最大数量的题目,小弟写的算法在其上编译器运行,得到的回应是超时.费尽脑汁也想不出好的算法了,只好来这里求助个位大侠,恳请
浙大acm题库1002求助
浙大acm题库,题号1002,那个有关设置火力点最大数量的题目,小弟写的算法在其上编译器运行,得到的回应是超时.费尽脑汁也想不出好的算法了,只好来这里求助个位大侠,恳请指点一二,感激不尽!
深度遍历?怎么能联系上呢?能说得详细些么?
我的代码本来是用队列控制的,为了省时间,改成数组了,也不行
能说一下思路么?然后我想自己写,
代码贴补不上了,有字数限制
浙大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 < n; i++)scanf("%s",&map[i]);
dfs(map,n,0,0,firenet);
printf("%d\n",firenet);
}
return 0;
}