【搜索】蓝桥杯原题:剪格子 - 木东驿站 - Powered by MoodBlog

CONTENT

【搜索】蓝桥杯原题:剪格子

问题描述 

如下图所示,3  x  3  的格子中填写了一些整数。 
+--*--+--+ 
|10*  1|52| 
+--****--+ 
|20|30*  1| 
*******--+ 
|  1|  2|  3| 
+--+--+--+  
我们沿着图中的星号线剪开,得到两个部分,每个部分的数字和都是60。 
本题的要求就是请你编程判定:对给定的m  x  n  的格子中的整数,是否可以分割为两个部分,使得这两个区域的数字和相等。 
如果存在多种解答,请输出包含左上角格子的那个区域包含的格子的最小数目。  
如果无法分割,则输出  0。 

输入

程序先读入两个整数  m  n  用空格分割  (m,n< 10)。 
表示表格的宽度和高度。 
接下来是n行,每行m个正整数,用空格分开。每个整数不大于10000。 

输出

输出一个整数,表示在所有解中,包含左上角的分割区可能包含的最小的格子数目。 

样例输入

3  3
10  1  52
20  30  1
1  2  3  

样例输出

3

import java.util.Scanner;
public class Main{ 
	static int n,m;
	static int num=0;
	static Data[][] data;
	static int min = 9999;
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		n=scanner.nextInt();
		m=scanner.nextInt();
		data = new Data[m][n];
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				data[i][j] = new Data();
				data[i][j].data = scanner.nextInt();
				num+=data[i][j].data;
			}
		}
		dfs(0,0,data[0][0].data,0);
		System.out.println(min+1);
	}
	static void dfs(int x,int y,int sum,int nrect){
		if(data[y][x].ispass!=0){
			return;
		}
		if(sum==num/2){
			if(min>nrect){
				min = nrect;
			}
			return;
		}
		//四方向行走
		data[y][x].ispass = 1;
		int tx = x,ty = y;
		if(tx+1<n){
			dfs(tx+1,ty,sum+data[ty][tx+1].data,nrect+1);
		}
		if(tx-1>=0){
			dfs(tx-1,ty,sum+data[ty][tx-1].data,nrect+1);
		}
		if(ty+1<m){
			dfs(tx,ty+1,sum+data[ty+1][tx].data,nrect+1);
		}
		if(ty-1>=0){
			dfs(tx,ty-1,sum+data[ty-1][tx].data,nrect+1);
		}
		data[y][x].ispass = 0;
	}
}
class Data{
	int data=0;
	int ispass=0;
}


个快快 2017年11月11日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号