Fork me on GitHub

剪格子 简单的DFS

读万卷书,行万里路
1
2
3
4
5
6
7
8
9
如下图所示,3 x 3 的格子中填写了一些整数。
+--*--+--+
|10* 1|52|
+--****--+
|20|30* 1|
*******--+
| 1| 2| 3|
+--+--+--+
我们沿着图中的星号线剪开,得到两个部分,每个部分的数字和都是60......

问题描述

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

注意这个题先输入的是列,然后是行

python版代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date : 2018-03-31 10:20:40
# @Author : wushilong
# @Email : 1320185818@qq.com | longofo.wu@gmail.com
# @Link : http://longofo.cc


class CutLatticeProblem:
'''
格子剪切问题
'''
def __init__(self, row, col, map_lst):
self.row = row # 行
self.col = col # 列
self.map_lst = map_lst # 格子列表
self.dirc = [(1, 0), (-1, 0), (0, -1), (0, 1)] # 方向:上下左右
self.visited = [[False] * col for _ in range(row)] # 初始化标志列表
self.sum = sum([sum(item) for item in map_lst]) # 计算矩阵总和
self.min_count = float('inf') # 定义一个无穷大的数

def judge(self, x, y):
'''
判断坐标是否超出格子列表
'''
if x < 0 or x >= self.row or y < 0 or y >= self.col:
return False
return True

def dfs(self, posx, posy, add, count):
'''
采用深度优先遍历
'''
if add == self.sum / 2:
# 这里min_count的值就是左上角围成的数字的数目,因为一开始就是从左上角开始的
if count < self.min_count:
self.min_count = count
return
for dic in self.dirc:
next_x, next_y = posx + dic[0], posy + dic[1]

if not self.judge(next_x, next_y):
continue
# 如果没有访问并且当前经过路径的总和小于等于总和的一半,继续遍历下去
if not self.visited[next_x][next_y] and (add + self.map_lst[next_x][next_y]) <= self.sum / 2:
self.visited[next_x][next_y] = True #标记访问
self.dfs(next_x, next_y, add +
self.map_lst[next_x][next_y], count + 1)
self.visited[next_x][next_y] = False #回溯

def main(self):
# 如果总和为奇数,那么一定找不到合理的方案
if self.sum % 2 == 1:
print(0)

self.dfs(0, 0, self.map_lst[0][0], 1)

if self.min_count == float('inf'):
print(0)
else:
print(self.min_count)


if __name__ == '__main__':
col = int(input('input col:'))
row = int(input('input row:'))
map_lst = [[0] * col for _ in range(row)]
print('input a {0} row {1} col 矩阵:'.format(row, col))
for x in range(row):
cols = input().split(' ')
for y in range(col):
map_lst[x][y] = int(cols[y])
cut_lattice = CutLatticeProblem(row, col, map_lst)
cut_lattice.main()

c++版代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cstdio>  
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std ;

int ans = INT_MAX ; //定义整型最大值
const int dir[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};//方向
int map[15][15] , sum = 0;//保存格子
bool visited[15][15] ;//标志访问
int row,col ;//行列
bool judge(int x , int y)
{
//判断是否越界
if(x<0||y<0||x>=row||y>=col)
{
return false ;
}
return true ;
}

void DFS(int x , int y , int add , int count)
{
//深度优先遍历
if(add == sum/2)
{
if(count<ans)
{
//这里count就是左上角区域的数目,因为一开始就是从左上角开始的
ans = count ;
}
return ;
}
for(int i = 0 ; i < 4 ; ++i)
{
int nextX = x + dir[i][0] , nextY = y + dir[i][1] ;
if(!judge(nextX,nextY))
{
continue ;
}
if(!visited[nextX][nextY]&&add+map[nextX][nextY]<=sum/2)//没有访问过并且和小于等于总和的一般
{
visited[nextX][nextY] = true ; //标志访问过
DFS(nextX,nextY,add+map[nextX][nextY],count+1) ;
visited[nextX][nextY] = false ; //回溯
}
}
}

int main()
{
while(scanf("%d%d",&col,&row) != EOF)
{
sum = 0 ;
//注意是先输入的列,在输入的行
for(int i = 0 ; i < row ; ++i)
{
for(int j = 0 ; j < col ; ++j)
{
scanf("%d",&map[i][j]) ;
sum += map[i][j] ;
}
}
if(sum%2 == 1)
{ //和为奇数一定没结果的
printf("0\n") ;
continue ;
}
memset(visited,false,sizeof(visited)) ; //初始化
ans = INT_MAX ;
DFS(0,0,map[0][0],1) ;
if(ans == INT_MAX)
printf("0\n") ;
else
printf("%d\n",ans) ;
}
return 0 ;
}
-------------本文结束感谢您的阅读-------------

本文标题:剪格子 简单的DFS

文章作者:Longofo

发布时间:2018年03月31日 - 11:03

最后更新:2018年03月31日 - 12:03

原始链接:http://longofo.cc/剪格子 简单的DFS.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我吃包辣条也好啊!!!
分享到: