技术标签： DFS sicily 算法设计与原理练习题
对于一个01矩阵A，求其中有多少片连成一片的1. 每个1可以和上下左右的1相连.
请为下面的Solution类实现解决这一问题的函数countConnectedOnes，函数参数A为给出的01矩阵，A的行数和列数均不大于1000. 函数的返回值是问题的答案.
class Solution {
public:
int countConnectedOnes(vector<vector <char>>& A) {
}
};
例1：
A=
100
010
001
答案为3.
例2：
A=
1101
0101
1110
答案为2.
依题意需要查找一个矩阵中的连通分量，从坐标[0][0]的点开始对矩阵DFS遍历，遇到为1的点时，联通分量的个数count加一，将该点的值修改为3，并对该点前后左右的点继续进行DFS；遇到为0或为3的点则跳过。
一开始我只设定DFS的方向朝右下方进行，忽略了可能与左下方相连的点，导致联通分量数目增加，后来修改为对(k + 1, j)，(k - 1, j)，(k, j+ 1)，(k, j - 1)四个方向的相邻点都遍历。
class Solution {
public:
int countConnectedOnes(vector<vector<char> >& A) {
if(A.size() == 0) return 0;
int count = 0;
for(int i = 0; i < A.size(); i++){
for(int j = 0; j < A[0].size(); j++){
if(A[i][j] == '1' ){
count++;
connect(A, i, j);
}
}
}
return count;
}
void connect(vector<vector<char> > & A, int k, int l){
A[k][l] = '3';
if(k < A.size() - 1 && A[k + 1][l] == '1') connect(A, k + 1, l);
if(l < A[0].size() - 1 && A[k][l + 1] == '1') connect(A, k , l + 1);
if(k > 0 && A[k - 1][l] == '1') connect(A, k - 1, l);
if(l > 0 && A[k][l - 1] == '1') connect(A, k , l - 1);
}
}; 文章浏览阅读251次。如果您只是加入本系列，我们一直在讨论代码气味，如何重构它们的话题，以及可用来帮助我们自动完成随之而来的一些单调性的工具，尤其是在PHP编程中。 如果您还没有阅读本系列的前两篇文章，我建议您这样做，因为它们涵盖了我们在继续本文其余部分之前已经具备的一些先决条件。 这些文章是： 将PHP CodeSniffer与WordPress结合使用：了解代码气味 将PHP CodeSnif..._"/vendor/bin/phpcs\" --version"
文章浏览阅读559次。点击蓝色字体“肉眼品世界”，关注公众号深度价值体系传递文|技术领导力社区中台组编辑| Emma01腾讯：中台战略，All in产业互联网自去年CSIG成立以来，腾讯通..._小米 中台建设 瓶颈
文章浏览阅读9.9k次，点赞3次，收藏4次。List<String> useridList = new ArrayList<>(); //需要注意的是这个位置 new ArrayList<>(); useridList 存的是 not in 中的参数Repository 接口中方法第一种带分页public Page<UserEntity> findByIdNotIn(..._jpa not in
文章浏览阅读3.4k次。近日笔者在一台linux服务器上安装vnc-server，却莫名奇妙的遇到了以下问题；错误：解压压缩文件在文件/etc/rc.d/init.d/vncserver;56655132失败：cpio:open失败-没有那个文件或目录错误：vnc-server-4.1.2-14.el5_6.6.x86_64:安裝已失败我最先关注的是这个错误：没有那个文件或目录，这个错误在linux操..._cpio: open
文章浏览阅读3.5k次。测试代码才能真正体现开发人员的水平。追求技术卓越是采用敏捷的第一成功要素。—— Jeff Sutherland 敏捷宣言创始人之一Phodal: “你为什么写测试？”开发人员 A：“为了..._代码检测 坏味道
文章浏览阅读744次，点赞21次，收藏27次。程序员API百宝箱，含各类热门好用的API
文章浏览阅读81次。临时允许ping命令可使用命令：echo 0 >/proc/sys/net/ipv4/icmp_ignore_all :0，代表允许；1，代表禁止1，查看当前设置：[root@k4622v /root]# more /proc/sys/net/ipv4/icmp_echo_ignore_all0科技看到为0，为此我们可以ping一下试试2，使用ping命令测试C:\Users\adminis..._linux开通ping策略
文章浏览阅读291次。IDC许可证有地网和全网之分，地网在公司所在地通信管理局申请，全网在中华人民共和国工业和信息化部申请。一、申请企业要满足四项基本条件（涉及到地网，因各地通信管理局会根据本地具体业务发展情况制定特色要求，下列关于地网的要求仅供参考，个别省份未必适用）：1、注册资金全网1000万元（实缴认缴均可），地网100万元（实缴认缴均可）；2、申请公司至少要有三名员工并且可以提供近一个月的社保证明（需申请主体自行缴纳，劳务派遣不可）；3、申请公司股东逐级追溯不得包含外资成分，注意是逐级追溯，也就是说你股东的_idc业务年报申报
文章浏览阅读4.3k次，点赞4次，收藏12次。6-1 快速排序 (15分)给一个无序表，使用快速排序算法对它进行排序。函数接口定义：int Partition(SqList &L,int low,int high); void QuickSort(SqList &L, int low, int high);其中L是待排序表，low和high是排序的区间。裁判测试程序样例：#include <iostre..._给一个无序表,使用快速排序算法对它进行排序。 函数接口定义: int partition(sqli
文章浏览阅读4.5k次，点赞81次，收藏240次。IDEA git操作大全，cherry pick、revert、squash等等，持续更新中......_idea上的git操作
文章浏览阅读322次。介质版本:Python 3.6Sublime Text 3包括：sublime字体配置。常用插件：Package Control、SublimeCodeIntel、SublimeREPL、SublimeTmpl、ColorSublime、Anaconda、SublimeLinter1、sublime基本配置。配置python路径：击New Build System后，会生成一个空配置文件，在这个配..._sublime text 新建的配置文件找不到
文章浏览阅读5.8k次，点赞8次，收藏55次。element - 饿了么出品的Vue2的web UI工具套件mint-ui - Vue 2的移动UI元素- 基于 Vuejs 的开源 UI 组件库Keen-UI - 轻量级的基本UI组件合集vue-material - 通过Vue Material和Vue 2建立精美的app应用muse-ui - 三端样式一致的响应式 UI 库vuetify - 为移动而生的Vue JS 2组件框架vonic - 快速构建移动端单页应用vue-blu - 帮助你轻松创建web应用。_vue插件