网易 魔法王国编程题,AC60%,求大佬看看哪里有问题

#include <iostream>
#include <vector>
using namespace std;
#define VISITED 2
int n;
int L;
int maze[50][50];
int maxnum;
void dfs(int i, int j, int length)
{
L--;
bool temp = false;
for (int m = 0; m < n; m++)
{
if (maze[j][m]==2)
{
temp = true;
break;
}

}
if (!temp)
{
length++;
}
maze[j][i]=maze[i][j] = VISITED;
if (L == 0) {
if (length > maxnum) {
maxnum = length;
}
return;
}
if (L > 0) {
for (int nx = 0; nx < n; ++nx) {
if (maze[j][nx] != 0)
{
int temp = maze[j][nx];
dfs(j, nx, length);
maze[j][nx]=maze[nx][j] = temp;    // 注意:之前maze[x][y]被标记为VISITED(值为2),回退后应该将其还原为1
L++;
}
}
}
return;
}
int main()
{
cin >> n >> L;
int temp;
for (int i = 0; i<n; i++)
{
for (int j = 0; j<n; j++)
{
maze[i][j] = 0;
}
}
for (int i = 0; i <= n - 2; i++)
{
cin >> temp;
maze[i + 1][temp] = 1;
maze[temp][i + 1] = 1;
}
maxnum = 1;
for (int i = 0; i < n; i++)
{
if (maze[0][i] == 1)
{
dfs(0, i, 1);
}
}
cout << maxnum;
return 0;
}
全部评论
深搜时间复杂度太高,他就是棵树,算路径长度就行了。(然而时间没来得及改)
点赞 回复 分享
发布于 2017-09-09 17:22
这个不是暴力解的啊。 可以这样想,除了起点外,要访问其它节点,就必须消耗left的值,访问一个节点,消耗left的值可能是1,也可能是2,但你总可以找到合理的方案,使得一条路不会重复走超过2次,所以left的值不可能超过2了。要想尽可能多的访问城市,那么就得要尽可能多的访问那些消耗left值为1的点。事实上,消耗left为1的点最多不超过树的深度,所以。。。如果你的left小于树的深度,那么访问城市的数量就是left+1,否则,就是(left-deep)/2+deep+1,其中,deep是树的最大深度。deep就用深度有限搜索求。。。
点赞 回复 分享
发布于 2017-09-09 19:45

相关推荐

10-07 23:57
已编辑
电子科技大学 Java
八街九陌:博士?客户端?开发?啊?
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务