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

import java.util.Scanner;

public class Main {

	private static int m, n, ans = Integer.MAX_VALUE;
	private static int nums;
	private static int[][] dis, Grid;
	private static int[] dx = { 1, 0, -1, 0 }, dy = { 0, -1, 0, 1 };

	public static void main(String[] args) {

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

		Grid = new int[n][m];
		nums = 0;

		dis = new int[n][m];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				Grid[i][j] = sc.nextInt();
				nums += Grid[i][j];
			}
		}

		CutGrid(0, 0, 0, 0);

		System.out.println(ans);

	}

	public static void CutGrid(int x, int y, int cut, int steap) {	
		
		if (cut == nums / 2) {
			ans = Math.min(ans, steap);
			return;
		}

		if (cut > nums / 2) {
			return;
		}
		
		dis[x][y] = -1;   //标记已访问
		cut += Grid[x][y];  //累加

		for (int i = 0; i < dx.length; i++) {
			int tx = x + dx[i];
			int ty = y + dy[i];
			if (tx >= 0 && tx < n && ty >= 0 && ty < m && dis[tx][ty] == 0) {				
				CutGrid(tx, ty, cut, steap + 1);
				dis[tx][ty] = 0;
			}
		}
		

	}

}

解题思路:

注意事项:

参考代码: