取数游戏
题目描述
一个$N \times M$的由非负整数构成的数字矩阵,你需要在其中取出若干个数字,使得取出的任意两个数字不相邻(若一个数字在另外一个数字相邻$8$个格子中的一个即认为这两个数字相邻),求取出数字和最大是多少。
输入格式
第1行有一个正整数$T$,表示了有$T$组数据。
对于每一组数据,第一行有两个正整数$N$和$M$,表示了数字矩阵为$N$行$M$列。
接下来$N$行,每行$M$个非负整数,描述了这个数字矩阵。
输出格式
$T$行,每行一个非负整数,输出所求得的答案。
样例 #1
样例输入 #1
3
4 4
67 75 63 10
29 29 92 14
21 68 71 56
8 67 91 25
2 3
87 70 85
10 3 17
3 3
1 1 1
1 99 1
1 1 1
样例输出 #1
271
172
99
提示
对于第1组数据,取数方式如下:
[67] 75 63 10
29 29 [92] 14
[21] 68 71 56
8 67 [91] 25
对于$20\%$的数据,$N, M≤3$;
对于$40\%$的数据,$N,M≤4$;
对于$60\%$的数据,$N, M≤5$;
对于$100\%$的数据,$N, M≤6,T≤20$。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
/**************** 以下为快读 ****************/
static BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer in;
// 在没有其他输入时返回 null
static String next() {
try {
while (in == null || !in.hasMoreTokens())
in = new StringTokenizer(r.readLine());
return in.nextToken();
} catch (Exception e) {
}
return null;
}
static int nextInt() {
return Integer.parseInt(next());
}
static double nextDouble() {
return Double.parseDouble(next());
}
static long nextLong() {
return Long.parseLong(next());
}
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static final int N = 10;
static int t, n, m, max;
static int[][] g = new int[N][N];
static boolean[][] vis = new boolean[N][N];
static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
static void dfs(int x, int y, int sum) {
if(y > m) {
x += 1;
y = 1;
}
if(x > n) {
max = Math.max(max, sum);
return;
}
dfs(x, y + 1, sum);//不选当前这个数, 不用判断可以不可以选它
if(judge(x, y)) {//选这个数,首先得判断是不是能选
vis[x][y] = true;
dfs(x, y + 1, sum + g[x][y]);
vis[x][y] = false;
}
}
static boolean judge(int x, int y) {//判断这个数的八个方位是不是被选过,因为周围八个都没被选过他才能被选
if(vis[x][y] == true) return false;
else {
for(int i = 0;i < 8;i ++) {
int xx = x + dx[i];
int yy = y + dy[i];
if(xx >= 1 && xx <= n && yy >= 1 && yy <= m && vis[xx][yy]) return false;
//如果它附近八个之内有被选了的 就返回false
}
}
return true;
}
public static void main(String[] args) throws Exception{
t = nextInt();//t组数据
while (t -- > 0) {
n = nextInt();//n行
m = nextInt();//m列
g = new int[N][N];
vis = new boolean[N][N];//重新初始化数据
for(int i = 1;i <= n;i ++) {
for(int j = 1;j <= m;j ++) {
g[i][j] = nextInt();
}
}
dfs(1, 1, 0);
out.print(max + "\n");
max = 0;
}
out.flush();
out.close();
}
}