前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >蓝桥杯-剪格子

蓝桥杯-剪格子

作者头像
用户10271432
发布2023-03-09 20:18:11
3600
发布2023-03-09 20:18:11
举报

没有白走的路,每一步都算数🎈🎈🎈

题目描述:

已知一个方格,有n行m列,这个方格中的每个位置都标满了数字,问是否可以把这个方格分成两个部分,这两个部分的所有数字之和是相同的。如果可以并且有多种方案,则输出左上角的部分,经过的方格数最小的方法。否则输出0。

输入描述:

第一行:

n,m表示行数和列数

第二行:

输入n行m列的所有数据,每个数据用空格分开

输出描述:

输出最小方案数

样例输入输出:

样例输入:

3 3

10 1 52

20 30

1 1 2 3

样例输出:

3

算法:

代码语言:javascript
复制
import os
import sys
ans = 0
m,n = map(int,input().split())
mp = [[int(j)for j in input().split()]for i in range(n)]
flag = [[0]*(m)for i in range(n)]
for i in range(n):
    for j in range(m):
        ans+=mp[i][j]
z = []
d = [[1,0],[-1,0],[0,1],[0,-1]]
def dfs(x,y,res,cnt):
    if res == ans//2:
        z.append(cnt)
        return
    for a,b in d:
        newx,newy = x+a,y+b
        if newx>=0 and newx<n and newy>=0 and newy<m \
           and flag[newx][newy]==0:
            cnt+=1
            res+=mp[newx][newy]
            flag[x][y] = 1
            dfs(newx,newy,res,cnt)
            res-=mp[newx][newy]
            flag[x][y] = 0
            cnt-=1
if ans%2 !=0:
    print(0)       
else:
    dfs(0,0,mp[0][0],1)
    print(min(z))
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-03-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 输入描述:
  • 输出描述:
  • 样例输入输出:
  • 算法:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档