题目描述
如图p1.jpg所示，3 x 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
再例如：
用户输入：
4 3
1 1 1 1
1 30 80 2
1 1 1 100
则程序输出：
10
(参见p2.jpg)
资源约定：
峰值内存消耗（含虚拟机） < 64M
CPU消耗 < 5000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
PS：
1.输入m行n列,存入二维数组arr[n][m]及一维数组array[m*n]
2.总价为奇数时,输出0.总价为偶数时,到步骤3.
3.用动态规划得到总和为count/2的最优解,每次得到最优解时进行步骤4的验证.
4.将步骤3得到的最优解记录到一个flag[m][n]中,对标记在flag中的格子进行深度遍历,若连通说明符合条件,然后对未被标记在flag中的格子也进行深度遍历,若连通说明格子确实被分成了两部分而不是更多的部分.这样就成功验证了.
5.输出步骤3中验证成功并且最终最优的那个解的格子数.
注意,这道题难点在于剪开的必须是"两部分",如果是其中一部分是连通的,但可能把另一部分截断,如:
4 4
20 30 40 1
110 1 10 1
1 2 10 1
1 1 10 1
这种情况是不符合的,而且很难验证.本程序反过来先算值为total/2的两部分,然后分别计算连通,这种思路比较清晰.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class t9 {
static int n,m;
static int[][] arr;
static int[] array;
static boolean[][] flag;
static boolean[][] visit;
static int total=0;
static int result=0;
static int finalResult=Integer.MAX_VALUE;
static int index=0;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
Scanner sc2=new Scanner(sc.nextLine()).useDelimiter("\s*");
m=sc2.nextInt(); //列
n=sc2.nextInt(); //行
arr=new int[n][m];
array=new int[n*m];
flag=new boolean[n][m];
for(int i=0;i<n;i++){
sc2=new Scanner(sc.nextLine());
for(int j=0;j<m;j++){
arr[i][j]=sc2.nextInt();
array[index++]=arr[i][j];
total+=arr[i][j];
}
}
if(total%2!=0 || array[0]>total/2){ //奇数不可分割
System.out.println(0);
}else{
flag[0][0]=true;
result++;
dp(total/2-array[0],1);
if(finalResult==Integer.MAX_VALUE) finalResult=0;
System.out.println(finalResult);
}
}
public static void dp(int count, int start){ //动态规划,找到和等于total/2的情况并验证,取最优解
if(count==0){ //和为total/2的情况
if(confirm() && finalResult>result){
finalResult=result; //验证并取最优解
return;
}
}
for(int i=start;i<index;i++){
if(count>=array[i]){
count-=array[i];
flag[i/m][i%m]=true; //访问过,标记
result++;
dp(count,i+1); //..i+1
count+=array[i]; //退栈时注意还原
flag[i/m][i%m]=false;
result--;
}
}
}
public static boolean confirm(){ //验证是否是连通图
for(int i=0;i<n;i++){ //..打印这种情况
for(int j=0;j<m;j++){
System.out.print(flag[i][j]+" ");
}
System.out.println();
}
System.out.println();
int row=0,col=0;
visit=new boolean[n][m];
for(int i=1;i<index;i++){ //找到一个属于"另一部分"的方格
if(flag[i/m][i%m]==false){
row=i/m;
col=i%m;
break;
}
}
if(dfs(0,0,1)==result && dfs(row,col,0)==index-result){ //两部分都为连通图,则满足题意
return true;
}
else{
return false;
}
}
public static int dfs(int row, int col, int f){
int num1=0;
int num2=0;
int num3=0;
int num4=0;
if(f==1 && flag[row][col]==true){ //包含左上角方块的部分
visit[row][col]=true;
if(row+1<n && !visit[row+1][col]) num1=dfs(row+1,col,1);
if(col+1<m && !visit[row][col+1]) num2=dfs(row,col+1,1);
return num1+num2+1;
}else if(f==0 && flag[row][col]==false){ //另外一部分
visit[row][col]=true;
if(row+1<n && !visit[row+1][col]) num1=dfs(row+1,col,0);
if(col+1<m && !visit[row][col+1]) num2=dfs(row,col+1,0);
if(row-1>=0 && !visit[row-1][col]) num3=dfs(row-1,col,0);
if(col-1>=0 && !visit[row][col-1]) num4=dfs(row,col-1,0);
return num1+num2+num3+num4+1;
}else{
return 0;
}
}
}