为什么我将数组的类型由int型改为bool型就无法通过? 这是AC的代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n,m,t;
int g[N][N];
int st[N][N];
int dx[] = {0,-1,-1,-1,0,1,1,1},dy[] = {1,1,0,-1,-1,-1,0,1};
long long ans = -1;
void dfs(int x,int y,long long sum)
{
if (y > m) x ++, y = 1;
if (x > n)
{
ans = max (ans,sum);
return ;
}
//这个点不选
dfs(x,y + 1,sum);
//这个点选
if (!st[x][y])
{
for (int i = 0; i < 8;i ++ )
{
int a = x + dx[i];
int b = y + dy[i];
if (a < 1 || a > n || b < 1 || b > m) continue;
st[a][b] ++;
}
dfs(x,y + 1,sum + g[x][y]);
for (int i = 0; i < 8;i ++ )
{
int a = x + dx[i];
int b = y + dy[i];
if (a < 1 || a > n || b < 1 || b > m) continue;
st[a][b] --;
}
}
}
int main()
{
scanf("%d",&t);
while (t -- )
{
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i ++ )
for (int j =1;j <= m;j ++ )
scanf("%d",&g[i][j]);
memset(st,0,sizeof st);
ans = -1;
dfs(1,1,0);
printf("%lld\n",ans);
}
return 0;
}
可为啥我将st数组改为bool型就过不了:
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n,m,t;
int g[N][N];
bool st[N][N];
int dx[] = {0,-1,-1,-1,0,1,1,1},dy[] = {1,1,0,-1,-1,-1,0,1};
long long ans = -1;
void dfs(int x,int y,long long sum)
{
if (y > m) x ++, y = 1;
if (x > n)
{
ans = max (ans,sum);
return ;
}
//这个点不选
dfs(x,y + 1,sum);
//这个点选
if (!st[x][y])
{
for (int i = 0; i < 8;i ++ )
{
int a = x + dx[i];
int b = y + dy[i];
if (a < 1 || a > n || b < 1 || b > m) continue;
st[a][b]= true;
}
dfs(x,y + 1,sum + g[x][y]);
for (int i = 0; i < 8;i ++ )
{
int a = x + dx[i];
int b = y + dy[i];
if (a < 1 || a > n || b < 1 || b > m) continue;
st[a][b] = false;
}
}
}
int main()
{
scanf("%d",&t);
while (t -- )
{
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i ++ )
for (int j =1;j <= m;j ++ )
scanf("%d",&g[i][j]),st[i][j] = false;
// memset(st,false,sizeof st);
ans = -1;
dfs(1,1,0);
printf("%lld\n",ans);
}
return 0;
}