#include <stdio.h> #define H 20000 //标记值 int m,n; int map[10][10]; //图 int aim = 0; //目标数值 int sum = 0; //当前数值总和 int count = 0; //当前步数 int min = 1<<30; //记录最小步数 void dfs(int i, int j) //深搜 { int tem = map[i][j]; //记录该点的值,用于回溯 //如果该点在边界,并且不在两端,并且相邻的两个点都是没走过的,这步不能走,回退 if ((i == 0 || i == m-1) && j > 0 && j < n-1 && map[i][j+1] != H && map[i][j-1] != H) return ; if ((j == 0 || j == n-1) && i > 0 && i < m-1 && map[i+1][j] != H && map[i-1][j] != H) return ; sum += tem; //加数值 count++; //加步数 if (sum == aim) //如果是目标数值,更新最小值并回溯 { min = count; sum -= tem; count--; return ; } map[i][j] = H; //标记 if (count < min) { //剪枝 if (j < n-1 && map[i][j+1] != H && sum + map[i][j+1] <= aim) dfs(i, j+1); if (j > 0 && map[i][j-1] != H && sum + map[i][j-1] <= aim) dfs(i, j-1); if (i < m-1 && map[i+1][j] !=H && sum + map[i+1][j] <= aim) dfs(i+1, j); if (i > 0 && map[i-1][j] != H && sum + map[i-1][j] <= aim) dfs(i-1 ,j); } //回溯 sum -= tem; count--; map[i][j] = tem; } int main() { int i, j; scanf("%d%d",&n,&m); for (i = 0; i < m; i++) { for (j = 0; j < n; j++) { scanf("%d",&map[i][j]); aim += map[i][j]; } } if (aim % 2) //如果总和是奇数则怎么都剪不了 { printf("0"); return 0; } aim /= 2; dfs(0, 0); if (min != 1<<30) //如果最小值没被更新,则剪不了 printf("%d",min); else printf("0"); return 0; }
解题思路:
注意事项:
参考代码:
0.0分
0 人评分
计算质因子 (C++代码)100以内质数直接打表就好了浏览:1192 |
人见人爱A+B (C语言代码)浏览:1011 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:1237 |
假币问题 (C++代码)(向上取整的一种处理方式)浏览:1663 |
Tom数 (C语言代码)浏览:736 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:715 |
简单的a+b (C语言代码)浏览:723 |
C语言训练-谁家孩子跑最慢* (C语言代码)浏览:1508 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:604 |
简单的a+b (C语言代码)浏览:629 |