原题链接：蓝桥杯2013年第四届真题-剪格子
解题思路:
回溯+DFS
当搜索路径上的数字和等于矩阵总和的一半时说明找到了这样的一个分割，记录好走了多少步，保存步数最小的那个结果即可
注意事项:
记得状态恢复
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | public class Main { static int[][] arr; static int sum = 0; static int[][] go = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; static int[][] flag; static int m, n; static int res = Integer.MAX_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in); // m列n行 m = sc.nextInt(); n = sc.nextInt(); arr = new int[n][m]; flag = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { arr[i][j] = sc.nextInt(); sum += arr[i][j]; } } int x = 0, y = 0; flag[0][0] = 1; dfs(x, y, arr[0][0], 1); if (res != Integer.MAX_VALUE) { System.out.println(res); }else { System.out.println(0); } } private static void dfs(int x, int y, int account, int step) { if (account == sum / 2) { res = Math.min(step, res); return; } for (int j = 0; j < 4; j++) { int x1 = x + go[j][0]; int y1 = y + go[j][1]; if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && flag[x1][y1] != 1) { flag[x1][y1] = 1; dfs(x1, y1, account + arr[x1][y1], step + 1); flag[x1][y1] = 0; } } }} |
0 分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复