剪格子

电玩女神 2022-07-24 06:11 179阅读 0赞

如下图所示，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。

输出格式  
输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。  
样例输入1  
3 3  
10 1 52  
20 30 1  
1 2 3  
样例输出1  
3  
样例输入2  
4 3  
1 1 1 1  
1 30 80 2  
1 1 1 100  
样例输出2  
10  
\*  
\*  
\* 使用深搜！

import java.util.Scanner;
    
    public class Main {
    
        public static int m,n;
        public static int sum,ans;
        public static int[][] grids;
        public static int[] dirx = {
       0,0,-1,1};
        public static int[] diry = {-1,1,0,0};
        public static boolean[][] visited;
    
        public static void show(){
            System.out.println("output grids:");
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++) System.out.print(grids[i][j]+" ");
                System.out.println();
            }
        }
    
        public static boolean DFS(int x,int y,int amount,int step){
            if(amount==sum){
                //System.out.println(grids[x][y]);
                ans = step;
                return true;
            }
            else{
                int nx,ny;
                for(int i=0;i<4;i++){
                    nx = x + dirx[i];
                    ny = y + diry[i];
                    if(nx>=0&&nx<n&&ny>=0&&ny<m&&!visited[nx][ny]){
       //连续的
                        visited[nx][ny] = true;
                        if(DFS(nx, ny, amount+grids[nx][ny], step+1)){
                        // System.out.println(grids[nx][ny]);
                            return true;
                        }
                        visited[nx][ny] = false;
                    }
                }
                return false;
            }
        }
    
        //求最小的格子数目。
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            m = in.nextInt();
            n = in.nextInt();
            grids = new int[n+10][m+10];
            visited = new boolean[n+10][m+10];
            sum = 0;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    grids[i][j] = in.nextInt();
                    sum += grids[i][j];
                }
            }
            if(sum%2!=0){
                System.out.println(0);
                return ;
            }
            sum /= 2;
            visited[0][0] = true;
            ans = 0;
            DFS(0, 0, grids[0][0], 1);
            System.out.println(ans);
        }
    
    }