求大佬解疑
查看原帖
求大佬解疑
841612
xian_love楼主2024/12/1 14:58

为什么我将数组的类型由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;
}
2024/12/1 14:58
加载中...