蓝桥杯2013年第四届真题-剪格子-题解（Java代码）

我看不懂题目，拿深搜的模板一套，瞎做的了。

import java.awt.List;
import java.util.ArrayList;
import java.util.Scanner;
public class Main{
	public static int next[][]={{0,1},{-1,0},{0,-1},{1,0}};//寻找下一步 ，逆时针寻找
	public static int result=Integer.MAX_VALUE,sum=0;//result：结果。sum:所有格子的和。
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        int arr[][]=new int[n][m];//格子
        int flag[][]=new int[n][m];//做个标记，标记是否走过
        //输入
        for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length; j++) {
				arr[i][j]=sc.nextInt();
				sum+=arr[i][j];
			}
		}
        if (sum%2==0) {//所有格子的和相加为一个偶数，才可能存在两个相等的情况
        	 //开始搜索
            dfs(arr, 0, 0, flag, arr[0][0],1);
            if (result != Integer.MAX_VALUE) {//如果找到了一个结果
                System.out.println(result);
            }else {
                System.out.println(0);
            }
		}else {
			System.out.println(0);
		}
        
       
        
}
    public static void dfs(int arr[][],int x,int y,int flag[][],int halfSum,int dept) {
    	//System.out.println("halfSum:"+halfSum+"。。Sum:"+sum);
		if (halfSum*2==sum) {
			result=Math.min(result, dept);
			return;
		}
		for (int i = 0; i <4; i++) {
			int dx=x+next[i][0];
			int dy=y+next[i][1];
			if (dx>=0 && dx<arr.length && dy>=0 && dy<arr[0].length && flag[dx][dy]==0) {//未越界，未判断过
				flag[dx][dy]=1;
				halfSum+=arr[dx][dy]; 
				dfs(arr, dx, dy, flag, halfSum,dept+1);
				halfSum-=arr[dx][dy];//回溯
				flag[dx][dy]=0;//回溯
			}
		}
		return ;
	}
}