分享丨s
24
发布于 江西

import java.util.*;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int H = sc.nextInt();

int W = sc.nextInt();

int[][] A = new int[H][W];

int[][] B = new int[H][W];

for (int i = 0; i < H; i++) {

for (int j = 0; j < W; j++) {

A[i][j] = sc.nextInt();

}

}

for (int i = 0; i < H; i++) {

for (int j = 0; j < W; j++) {

B[i][j] = sc.nextInt();

}

}

// 路径最多经过 H + W - 1 个格子

int MAX = 80 * (H + W - 1);

// dp[j][k]:到达当前行第 j 列时,

// 是否能得到绝对差值 k

boolean[][] dp = new boolean[W][MAX + 1];

for (int i = 0; i < H; i++) {

for (int j = 0; j < W; j++) {

int d = Math.abs(A[i][j] - B[i][j]);

if (i == 0 && j == 0) {

dp[j][d] = true;

continue;

}

boolean[] next = new boolean[MAX + 1];

// 前一个格子的最大可能差值

int limit = 80 * (i + j);

// 从上方转移

if (i > 0) {

for (int k = 0; k <= limit; k++) {

if (dp[j][k]) {

next[k + d] = true;

next[Math.abs(k - d)] = true;

}

}

}

// 从左方转移

if (j > 0) {

for (int k = 0; k <= limit; k++) {

if (dp[j - 1][k]) {

next[k + d] = true;

next[Math.abs(k - d)] = true;

}

}

}

dp[j] = next;

}

}

// 找到终点能够达到的最小绝对差值

for (int k = 0; k <= MAX; k++) {

if (dp[W - 1][k]) {

System.out.println(k);

break;

}

}

sc.close();

}

}

评论 (0)