本文共 2229 字,大约阅读时间需要 7 分钟。
如下图所示,3 x 3 的格子中填写了一些整数。
我们沿着图中的星号线剪开,得到两个部分,每个部分的数字和都是60。
本题的要求就是请你编程判定:对给定的m x n 的格子中的整数,是否可以分割为两个部分,使得这两个区域的数字和相等。
如果存在多种解答,请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割,则输出 0。
程序先读入两个整数 m n 用空格分割 (m,n<10)。
表示表格的宽度和高度。
接下来是n行,每行m个正整数,用空格分开。每个整数不大于10000。
import java.util.Scanner;import java.util.TreeSet;public class 剪格子 { static int[][] arr = null; static boolean[][] map = null; static int flag = 0; static int count = 0; static TreeSetrecord = new TreeSet (); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int y = sc.nextInt(); int x = sc.nextInt(); arr = new int[x][y]; map = new boolean[x][y]; for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { arr[i][j] = sc.nextInt(); flag += arr[i][j]; } } dfs(0, 0, 0); System.out.println(record.first()); } // 0 上 1右 2下 3左 static void dfs(int sum, final int x, final int y) { if (sum == flag / 2) { count++; calcSum(); return; } if (sum > flag) { return; } int newX = 0, newY = 0; for (int i = 0; i < 4; i++) { if (!canGo(x, y, i)) continue; newX = x; newY = y; if (i == 0) { newX -= 1; } if (i == 1) { newY += 1; } if (i == 2) { newX += 1; } if (i == 3) { newY -= 1; } // 可以深入 if (!map[newX][newY]) { map[x][y] = true; dfs(sum + arr[x][y], newX, newY); map[x][y] = false; } } } // 0 上 1右 2下 3左 static boolean canGo(int x, int y, int aim) { if (x == 0 && aim == 0) return false; if (x == arr.length - 1 && aim == 2) return false; if (y == 0 && aim == 3) return false; if (y == arr[0].length - 1 && aim == 1) return false; return true; } static void calcSum() { boolean flag = map[0][0]; int sum = 0; for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { if (map[i][j] == flag) sum++; } } record.add(sum); }}
转载地址:http://dryvb.baihongyu.com/