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

解题思路:
回溯+DFS

当搜索路径上的数字和等于矩阵总和的一半时说明找到了这样的一个分割，记录好走了多少步，保存步数最小的那个结果即可

注意事项:
记得状态恢复
参考代码:

public class Main {

    static int[][] arr;
    static int sum = 0;
    static int[][] go = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    static int[][] flag;
    static int m, n;
    static int res = Integer.MAX_VALUE;


    public static void main(String[] args) {


        Scanner sc = new Scanner(System.in);
        // m列n行
        m = sc.nextInt();
        n = sc.nextInt();

        arr = new int[n][m];
        flag = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = sc.nextInt();
                sum += arr[i][j];
            }
        }

        int x = 0, y = 0;
        flag[0][0] = 1;

        dfs(x, y, arr[0][0], 1);
        if (res != Integer.MAX_VALUE) {
            System.out.println(res);
        }else {
            System.out.println(0);
        }
    }

    private static void dfs(int x, int y, int account, int step) {
        if (account == sum / 2) {
            res = Math.min(step, res);
            return;
        }
        for (int j = 0; j < 4; j++) {
            int x1 = x + go[j][0];
            int y1 = y + go[j][1];

            if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && flag[x1][y1] != 1) {
                flag[x1][y1] = 1;
                dfs(x1, y1, account + arr[x1][y1], step + 1);
                flag[x1][y1] = 0;
            }
        }
    }

}