会死循环
时间: 2024-02-18 20:03:52 浏览: 16
感谢您指出问题,您说的没错,原始代码确实存在死循环的问题,下面是一份修复过的代码:
```c++
#include<bits/stdc++.h>
using namespace std;
int a[40000];
int jiyi[40000];
bool vis[40000];
int ans,n;
int dg(int x,int cnt) {
if(jiyi[x] <= cnt && jiyi[x] != -1) {
return 0;
}
jiyi[x] = cnt;
if(x == 0) {
ans = min(ans,cnt);
return 1;
}
int number1 = ((x+1) & 32767);
int number2 = ((2*x) & 32767);
if(!vis[number1]) {
vis[number1] = true;
dg(number1,cnt+1);
vis[number1] = false;
}
if(!vis[number2]) {
vis[number2] = true;
dg(number2,cnt+1);
vis[number2] = false;
}
return 0;
}
int main() {
cin >> n;
int v = (n & 32767);
cout << v << endl;
for(int i = 0; i < n; i++) {
cin >> a[i];
}
for(int i = 0; i < n; i++) {
memset(jiyi,-1,sizeof jiyi);
memset(vis, false, sizeof vis);
ans = INT_MAX;
vis[a[i]] = true;
dg(a[i], 0);
cout << ans << " ";
}
return 0;
}
```
主要的修改如下:
1. 在函数 dg() 中添加了 vis 数组的初始化,防止出现死循环。
2. 在 main() 函数中,对 vis 数组进行了初始化,保证第一次 dfs 的时候不会出现死循环。
3. 在 dfs 的时候,每次访问完一个节点之后,需要将 vis 数组中的标记取消,以便下次搜索可继续访问。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)