- import java.util.Scanner;
- public class Main{
- static int sum1=0;
- static int sum2=0;
- static int sum=0;
- static int min=10000;
- static int m;
- static int n;
- static int array[][]=new int[10][10];
- public static void main(String[] args) {
- Scanner scanner=new Scanner(System.in);
- m=scanner.nextInt();
- n=scanner.nextInt();
- for (int i = 0; i <n; i++) {
- for (int j = 0; j <= m; j++) {
- if(j==0) {
- array[i][j]=0;
- continue;
- }
- array[i][j]=scanner.nextInt();
- }
- }
- sum(0);
- if(min==10000) {
- System.out.println(0);
- }
- else {
- System.out.println(min);
- }
- }
- public static void sum(int a)
- {
- if(a==n) {
- //System.out.println(sum1+"----"+sum2);
- if(sum1==sum2) {
- if(sum<min) {
- min=sum;
- }
- }
- }else {
- for (int i = 0; i <=m; i++) {
- sum2+=array[a][i];
- }
- int ss=sum1;
- for(int i=0;i<=m;i++) {
- sum1+=array[a][i];
- if(i!=0) sum++;
- sum2-=array[a][i];
- sum(a+1);
- }
- sum-=m;
- sum1=ss;
- }
- }
- }
运行这个代码, 我发现所给的测试用例答案都可以通过, 可是系统给的测试用例通过不了, 分析发现我的代码实现了每行所取的块都是连续的, 即不能跳着取, 比如下面的一种
- 1 1 1
- 1 8 1
- 1 1 1
我们可以把中间的 8 作为单独一块, 外面的作为另一块, 这样中间一行取的块是最左和最右的, 跳过了中间的 8, 但是我的代码是每行从左到右取, 所以出现了问题.
版本 2 的思路是仍然是 dfs, 不过是按着先右再上再左再下的步骤走这些格子, 左上角的格子出发, 一直向右走, 把走过的路标记, 到最顶端到达边界, 再向上走, 没路, 向左, 路已经走过, 则向下, 这样一直递归迭代下去, 直到遇到走过的格子总和为所有格子的总数的一半, 记录所包含的格子数, 继续递归迭代, 直到求得最小值解.
代码如下
- import java.util.Scanner;
- public class Main{
- static int map[][]=new int[20][20];
- static int vis[][]=new int[20][20];
- static int dx[]= {1,0,-1,0};
- static int dy[]= {0,1,0,-1};
- static int m,n,s;
- static int min1=9999999;
- static int ans=1;
- public static void main(String[] args) {
- Scanner scanner=new Scanner(System.in);
- m=scanner.nextInt();
- n=scanner.nextInt();
- int sum1=0;
- for (int i=0;i<n;i++)
- for (int j=0;j<m;j++)
- {
- map[i][j]=scanner.nextInt();
- sum1+=map[i][j];
- }
- if (sum1%2!=0)
- System.out.println(0);
- else if (sum1/2==map[0][0]) System.out.println(1);
- else
- {
- s=sum1/2;
- vis[0][0]=1;
- dfsn(0,0,map[0][0]);
- System.out.println(min1);
- }
- }
- static void dfsn(int x,int y,int sum)
- {
- if (sum==s)
- {
- if(ans<min1){
- min1=ans;
- }
- }
- int i;
- for (i=0;i<4;i++)
- {
- int nx=x+dx[i];
- int ny=y+dy[i];
- if (0<=nx && nx<n && 0<=ny && ny<m )
- {
- if (sum+map[nx][ny]<=s && vis[nx][ny]!=1)
- {
- vis[nx][ny]=1;
- ans++;
- int a=sum+map[nx][ny];
- dfsn(nx,ny,a);
- ans--;
- vis[nx][ny]=0;// 初始化标志
- }
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2971627.html