@[Maysoul](/user/409774) 我之前用bool数组的时候也出现过玄学问题
by _Mikasa @ 2023-04-14 15:48:09
@[Maysoul](/user/409774) @[_Mikasa](/user/400245)
就冲你俩这头像我就肯定帮忙!!!
二乃!三玖!(超大声)
by You_Quiet @ 2023-04-14 19:48:37
@[You_Quiet](/user/421736) 哼……才,才不是想感谢你呢
by Maysoul @ 2023-04-14 19:50:08
@[Maysoul](/user/409774) 所以,如果方便的话能把代码发我一份吗,我不想打一遍了QAQ
by You_Quiet @ 2023-04-14 19:52:59
@[You_Quiet](/user/421736)
这是完整版,其实我只想要解决上面的问题而已
```
//2023/4/14
//别着急,先通读一遍题目
//别忘了开long long
//写完先看一遍怎么降复杂度
//要么开全局变量要么给定初值
//想想看,有什么情况需要特判
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int num,ans;
int vis[15][15];
int a[15][15];
int offsetx[8]={-1,0,1,-1,1,-1,0,1};
int offsety[8]={-1,-1,-1,0,0,1,1,1};
int n,m;
void dfs(int x,int y)
{
if(y==m+1)
{
dfs(x+1,1);
return;
}
if(x==n+1)
{
ans=max(num,ans);
return;
}
dfs(x,y+1);
if(vis[x][y]==0)
{
for (int i=0;i<8;i++)
{
vis[x+offsetx[i]][y+offsety[i]]++;
}
num+=a[x][y];
dfs(x,y+1);
num-=a[x][y];
for (int i=0;i<8;i++)
{
vis[x+offsetx[i]][y+offsety[i]]-=1;
}
}
}
void sweep()
{
memset(a,0,sizeof(a));
memset(vis,0,sizeof(vis));
ans=0;
num=0;
}
int main()
{
int t;
cin>>t;
while(t--)
{
sweep();
cin>>n>>m;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
dfs(1,1);
cout<<ans<<endl;
}
return 0;
}
```
by Maysoul @ 2023-04-14 19:55:29
@[Maysoul](/user/409774) 嗯嗯,好的好的,稍等我一下
by You_Quiet @ 2023-04-14 19:56:36
@[Maysoul](/user/409774) 因为可能会有同时两个点使某个点无法选上,如图:
![](https://cdn.luogu.com.cn/upload/image_hosting/d5nyqp7v.png)
两个黄色的点都会使红色的点无法选上,但如果在搜完右下角的黄色节点就把红色节点的标记直接释放的话,是不正确的,因为左上角的黄色节点还没有搜完,当前递归的状态中红色点还是无法选上的
如果用bool类型的vis的话,会让本来叠了两层限制的红色节点只叠了一层限制
by You_Quiet @ 2023-04-14 20:04:49
@[Maysoul](/user/409774) 我可能说的有些苍白,(我表达能力不是很好
by You_Quiet @ 2023-04-14 20:05:43
@[Maysoul](/user/409774) 假使你走过多次,就不行了。举个例子。
```cpp
int cnt=0;
bool vis=false;
cout<<(bool)cnt<<' '<<vis<<endl;
cnt++;
vis=true;
cout<<(bool)cnt<<' '<<vis<<endl;
cnt++;
vis=true;
cout<<(bool)cnt<<' '<<vis<<endl;
cnt--;
vis=false;
cout<<(bool)cnt<<' '<<vis<<endl;
cnt--;
vis=false;
cout<<(bool)cnt<<' '<<vis<<endl;
```
结果是:
```cpp
0 0
1 1
1 1
1 0
0 0
```
在第 4 个处不同了。
~~(傲娇已经退环境了)~~
by robinyqc @ 2023-04-14 20:06:58
也就是说,bool 类型没有 int 类型储存的信息多。
by robinyqc @ 2023-04-14 20:08:12