初学dfs蒟蒻求助
  • 板块P1123 取数游戏
  • 楼主迟陌
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/7/7 12:14
  • 上次更新2023/11/3 11:13:07
查看原帖
初学dfs蒟蒻求助
160870
迟陌楼主2023/7/7 12:14

想参考一下题解的思路写一遍,结果输出全是444,感觉思路好像没错,但是这样写是错在哪儿了呢?为什么全是444?求大佬解答

#include<stdio.h>
int a[1001][1001];
int d[8][8];
int mx = -1,ans;
int mark[1001][1001] = { 0 };
int t;
int m, n;
int max(int a, int b)
{
    if (a >= b)
        return a;
    else
        return b;
}
void dfs(int x,int y)
{
    if (y >= n&&x>=m)//y方向搜完代表整个搜完,更新最大值
    {
        mx = max(mx, ans);
        return;
    }
    if (x >= m)
    {
        dfs(1, y + 1);//整行搜完换下一行
        return;
    }
    dfs(x + 1, y);//不取这个数,直接搜下一个
    if (mark[x][y] == 0)
    {
        ans += a[x][y];
        for (int i = 1; i <= 8; i++)
        {
            mark[x + d[i][1]][y + d[i][2]] = 1;//九宫格标记
        }
        dfs(x + 1, y);
        ans -= a[x][y];//回溯
        for (int i = 1; i <= 8; i++)
        {
            mark[x + d[i][1]][y + d[i][2]] = 0;//回溯
        }
    }
    
}
int read()
{
    char c = getchar();
    int s = 0,w = 1;
    while (c < '0' || c>'9')
    {
        if (c == '-')
            w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        s = s * 10 + c - '0';
        c = getchar();
    }
    return s * w;
}
int main()
{
    d[1][1] = -1; d[2][1] = 0; d[3][1] = 1; d[4][1] = -1; d[5][1] = 1; d[6][1] = -1; d[7][1] = 0; d[8][1] = 1;//每一个周围点的x位移
    d[1][2] = 1; d[2][2] = 1; d[3][2] = 1; d[4][2] = 0; d[5][2] = 0; d[6][2] = -1; d[7][2] = -1; d[8][2] = -1;//每一个周围点的y位移
    t = read();
    while (t>0)
    {
        m = read(); n = read();
        for (int i = 1; i <= m ; i++)
            for (int j = 1; j <= n ; j++)
                a[i][j] = read();
        dfs(1, 1);
        printf("%d\n", mx);
        t--;
    }
    return 0;
    
}
2023/7/7 12:14
加载中...