本文主要是介绍2013省赛---剪格子（递归深度搜索，），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
import java.util.Scanner;public class TestOne {static int[][] g;//输入的表格private static int n;//n行private static int m;//m列private static int minStep = Integer.MAX_VALUE; //存储最小格子数private static int total;//表格中的数据总和static int[][] vis;//访问标记。以访问的格子标记为1public static void main(String[] args) {Scanner sc = new Scanner(System.in);//1.输入行、列数(注意先输入列m)m = sc.nextInt();n = sc.nextInt();//2.输入表格中的数据g = new int[n][m];vis = new int[n][m];for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {g[i][j] = sc.nextInt();//vis[i][j] = 0;total+=g[i][j];}}//3.对表格进行深度搜索，寻找满足条件的最少格子数dfs(0,0,0,0); //0行0列，已走格子数0，已走格子的累加和0//4.输出最小的步数System.out.println(minStep);}/*(1)对表格中的数据进行深度搜索* （i,j）:开始访问的格子坐标* step：当前已访问的格子数目* sum:当前已访问的格子累加和* */private static void dfs(int i, int j, int step, int sum) {//1. i、j越界 或者 当前格子已访问 (不合法)if(i<0 || i==n ||j<0 || j==m || vis[i][j]==1) return;//2. 已将表格划分为元素和相等的两部分if(sum==total/2) {minStep = Math.min(minStep, step);return;}//3. 超过总元素和一半 （不合法）if(sum>total/2) { return;}vis[i][j] = 1; //访问g[i][j]dfs(i-1,j,step+1,sum+g[i][j]);//上dfs(i+1,j,step+1,sum+g[i][j]);//下dfs(i,j-1,step+1,sum+g[i][j]);//左dfs(i,j+1,step+1,sum+g[i][j]);//右vis[i][j] = 0; //回溯}}
这篇关于2013省赛---剪格子（递归深度搜索，）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
