想参考一下题解的思路写一遍,结果输出全是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;
}