浙大acm题库1002求助浙大acm题库,题号1002,那个有关设置火力点最大数量的题目,小弟写的算法在其上编译器运行,得到的回应是超时.费尽脑汁也想不出好的算法了,只好来这里求助个位大侠,恳请
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/02 06:27:24
![浙大acm题库1002求助浙大acm题库,题号1002,那个有关设置火力点最大数量的题目,小弟写的算法在其上编译器运行,得到的回应是超时.费尽脑汁也想不出好的算法了,只好来这里求助个位大侠,恳请](/uploads/image/z/8833293-45-3.jpg?t=%E6%B5%99%E5%A4%A7acm%E9%A2%98%E5%BA%931002%E6%B1%82%E5%8A%A9%E6%B5%99%E5%A4%A7acm%E9%A2%98%E5%BA%93%2C%E9%A2%98%E5%8F%B71002%2C%E9%82%A3%E4%B8%AA%E6%9C%89%E5%85%B3%E8%AE%BE%E7%BD%AE%E7%81%AB%E5%8A%9B%E7%82%B9%E6%9C%80%E5%A4%A7%E6%95%B0%E9%87%8F%E7%9A%84%E9%A2%98%E7%9B%AE%2C%E5%B0%8F%E5%BC%9F%E5%86%99%E7%9A%84%E7%AE%97%E6%B3%95%E5%9C%A8%E5%85%B6%E4%B8%8A%E7%BC%96%E8%AF%91%E5%99%A8%E8%BF%90%E8%A1%8C%2C%E5%BE%97%E5%88%B0%E7%9A%84%E5%9B%9E%E5%BA%94%E6%98%AF%E8%B6%85%E6%97%B6.%E8%B4%B9%E5%B0%BD%E8%84%91%E6%B1%81%E4%B9%9F%E6%83%B3%E4%B8%8D%E5%87%BA%E5%A5%BD%E7%9A%84%E7%AE%97%E6%B3%95%E4%BA%86%2C%E5%8F%AA%E5%A5%BD%E6%9D%A5%E8%BF%99%E9%87%8C%E6%B1%82%E5%8A%A9%E4%B8%AA%E4%BD%8D%E5%A4%A7%E4%BE%A0%2C%E6%81%B3%E8%AF%B7)
浙大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;
}