蓝桥杯PREV-4 剪格子 （搜索）

如下图所示，3 x 3 的格子中填写了一些整数。

我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。

本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。

如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。

如果无法分割，则输出 0。

程序先读入两个整数 m n 用空格分割 (m,n<10)。

表示表格的宽度和高度。

接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。

10

import java.util.Scanner;public class Main {	static int maxn = 10;	static int[][] g = new int[maxn][maxn];	static boolean[][] vis = new boolean[maxn][maxn];	static int m,n,sum,singSum,cnt;	static boolean isOk = false;	static int ans = Integer.MAX_VALUE;	static int[] dr = {-1,0,1,0};	static int[] dc = {0,1,0,-1};	public static void main(String[] args) {		Scanner scan = new Scanner(System.in);		m = scan.nextInt();		n = scan.nextInt();		for(int i=0;i<n;i++){			for(int j=0;j<m;j++){				g[i][j] = scan.nextInt();				sum+=g[i][j];			}		}		if(sum%2!=0){			System.out.PRintln(0);		}else{			dfs(0,0);			if(isOk){				System.out.println(ans);			}else{				System.out.println(0);			}		}	}		public static void dfs(int r,int c){		if(r<0||r>=n||c<0||c>=m)			return;		if(vis[r][c])			return;		if(singSum==sum/2){			isOk = true;			ans = ans>cnt?cnt:ans;			return;		}		vis[r][c] = true;		singSum+=g[r][c];		cnt++;		for(int i=0;i<4;i++){			dfs(r+dr[i],c+dc[i]);		}		cnt--;		singSum-=g[r][c];		vis[r][c] = false;;	}}