题目

这是一道简单的搜索题，考查的还是比较基础的东西，其时搜索有时候并不难写，主要是要想到怎么搜。比如这个题，如果想二维四个方向搜则没有头绪，反之因为搜索是用递归实现的，所以我们可以使用递归的特性，把大问题处理成小问题来解决。

所以我们可以用处理每一行的形式，把这一行的最大值求出来，再接着向下一行搜，中途再加上回溯操作，这道搜索就做完了。

\(Code\)

#include <iostream>

#include <cstdio>

#include <algorithm>c

#include <cstring>

using namespace std;

int t, n, m, data[10][10], vis[10][10], maxn, deep;

void dfs(int x, int y, int now)

{

	if (x > n)

	{

		maxn = max(maxn, now);

		return;

	}

	int nexy = y + 1, nex = x;

	if (nexy > m)

	{

		nexy = 1;

		nex++;

	}

	if (!vis[x][y] && !vis[x + 1][y] && !vis[x + 1][y - 1] && !vis[x + 1][y - 1] && !vis[x + 1][y + 1] && !vis[x][y - 1]  && !vis[x - 1][y + 1] && !vis[x][y + 1] &&  !vis[x - 1][y] && !vis[x - 1][y - 1])

	{

		vis[x][y] = 1;

		dfs(nex, nexy, now + data[x][y]);

		vis[x][y] = 0;

	}

	dfs(nex, nexy, now);

}

int main() {

//	vis[i][j] = 1, vis[i + 1][j + 1] = 1, vis[i + 1][j - 1] = 1, vis[i + 1][j] = 1, vis[i - 1][j - 1] = 1, vis[i - 1][j] = 1, vis[i - 1][j - 1] = 1, vis[i][j + 1] = 1, vis[i][j - 1] = 1;

	scanf("%d", &t);

	while (t--)

	{

		maxn = 0;

		scanf("%d%d", &n, &m);

		for (int i = 1; i <= n; i++)

			for (int j = 1; j <= m; j++)

				scanf("%d", &data[i][j]), vis[i][j] = 0;

		dfs(1, 0, 0);

		printf("%d\n", maxn);

	}

}

/*

1

3 3

1 1 1

1 99 1

1 1 1

*/