脉动打老虎
2020-09-02 08:47 门头沟学院 Java
关注
个人思路：
1.首先统计所有1的数量one_count，发现矩阵全部是1，直接返回矩阵size；全部是0，返回0
2.否则说明有士兵，也有空位可以供士兵移动。对每一个0，可以尝试把一个1换到这个位置，dfs搜索该区域，更新ans
3.如果最终ans比所有1的数量one_count还多1，说明填充的1是凭空填充的，填充后原来所有的1会联通。这时直接返回step1中统计的1的数量one_count，否则返回ans
结果：部分超时
原因分析：对于不同的0，可能连接了同一区域内不同位置的1，从而对同一区域进行了多次dfs搜索，产生了重复计算。参考别人的做法，可以对每块区域先记录连通数量，避免重复计算
查看原帖
1 评论
相关推荐
不愿透露姓名的神秘牛友
05-29 15:26
贺韦：呜呜呜呜真正的告别从来不是 “一刀两断”，而是 “我承认你曾照亮过我的生命，现在我要目送你去更远的地方” 点赞 评论 收藏
分享
04-07 09:01
大连工业大学 Java 
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 写给毕业5年后的自己 #
4952次浏览 104人参与
# 国央企笔面经互助 #
129890次浏览 1082人参与
# 华泰证券Fintech星战营 #
169388次浏览 196人参与
# 职场捅娄子大赛 #
323736次浏览 3295人参与
# 好好告别我的学生时代 #
48501次浏览 907人参与
# 一人一个landing小技巧 #
61138次浏览 972人参与
# 毕业季等于分手季吗 #
17517次浏览 223人参与
# 晒一下我的毕业照 #
35019次浏览 397人参与
# 海信求职进展汇总 #
65352次浏览 361人参与
# 如何缓解求职过程中的焦虑？ #
8235次浏览 106人参与
# 记录实习开销 #
31019次浏览 213人参与
# 如果今天是你的last day，你会怎么度过？ #
22978次浏览 199人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
108546次浏览 783人参与
# 毕业后不工作的日子里我在做什么 #
172059次浏览 1519人参与
# HR问：你期望的薪资是多少？如何回答 #
40353次浏览 527人参与
# 毕业租房也有小确幸 #
110201次浏览 4327人参与
# 视觉/交互/设计百问百答 #
43341次浏览 428人参与
# 2022毕业即失业取暖地 #
97147次浏览 651人参与
# 上班苦还是上学苦呢？ #
223204次浏览 1331人参与
# 大学最后一个寒假，我想…… #
38370次浏览 498人参与
# 制造业的秋招小结 #
87760次浏览 1602人参与