#include int m, n, half = 0, sum = 0, minValue = 100, count = 0, select = 0, tnum; int num[10][10] = {0}, flag[10][10] = {0}; int xzb[] = {-1, 1, 0, 0}; /*上下左右*/ int yzb[] = {0, 0, -1, 1}; int isok(int x, int y) /*判断传入的坐标值是否能被选入*/ { int yes = 0; /*不越界并且不超出和一半*/ if ((x >= n || x < 0) || (y >= m || y < 0) || (flag[x][y] == 1) || (sum + num[x][y] > half)) yes = 1; /*冲突*/ return yes; } void back(int value, int x, int y) /*执行回退处理*/ { if (x == 0 && y == 0) /*如果将num[0][0]回溯掉,则标记为未选入*/ select = 0; --count; sum -= value; flag[x][y] = 0; } void dfs(int value, int x, int y) /*dfs搜索*/ { int i, t1, t2; if (x == 0 && y == 0) /*主要用于B点开始的搜素,判断num[0][0]有没有被选入*/ select = 1; flag[x][y] = 1; /*标记为已走过*/ ++count; /*已走过点的个数*/ sum += value; /*已走过的点的和*/ if (sum == half) { if (select == 1) /*如果num[0,0]被选入,主要用于非[0,0]点开始的搜索*/ tnum = count; else tnum = n * m - count; minValue = minValue > tnum ? tnum : minValue; /*选出剪掉点数最少的方案*/ } else { for (i = 0; i < 4; ++i) /*按 上下左右 顺序遍历*/ { t1 = x + xzb[i]; /*引入t1,t2目的是使传入的x,y值不变,便于下面的回退*/ t2 = y + yzb[i]; if (isok(t1, t2) == 1) /*是否可走*/ continue; dfs(num[t1][t2], t1, t2); } } back(value, x, y); /*如果上下左右都不可走:回退*/ } int main() { int i, j, maxNum = 0, all = 0; scanf("%d%d", &m, &n); for (i = 0; i < n; ++i) for (j = 0; j < m; ++j) { scanf("%d", &num[i][j]); all += num[i][j]; /*all为总和*/ if (num[i][j] > maxNum) /*找出最大值*/ maxNum = num[i][j]; } if (all % 2 != 0 || maxNum > all / 2) /*如果和为基数或者最大值大于总和一半*/ printf("0\n"); else { half = all / 2; /*将格子每个点都作为起点搜索一遍,两个for循环*/ for (i = 0; i < n; ++i) for (j = 0; j < m; ++j) { select = 0; dfs(num[i][j], i, j); } if (minValue != 100) /*找不到*/ printf("%d\n", minValue); else printf("0\n"); } return 0; }