【编程题】一个只包含0和1的阵列，找到1的组的个数，每个组的_广联达笔试题

权_DV

public int method(int[][] matrix){
    int res = 0;
    if(matrix == null){
        return res;
    }
     
    for(int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[0].length;j++){
            if(matrix[i][j] == 1){
                dfs(matrix,i,j);
                                res++;
            }
        }
    }
    return res;
}
public void dfs(int[][] matrix,int i,int j){
    if(i<0 || j<0 || i>=matrix.length || j>=matrix[0].length || matrix[i][j]==0){
        return;
    }
    matrix[i][j]==0;
    dfs(matrix,i+1,j);
    dfs(matrix,i-1,j);
    dfs(matrix,i,j+1);
    dfs(matrix,i,j-1);
}

发表于 2020-04-29 01:23:25 回复(1)

jinbaowang

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int m,n;
    cin>>m>>n;
    vector<vector<int>> vec(m,vec<int>(n,0));
    for(int i=0;i<m;i++)
         for(int j=0;j<n;j++)
             cin>>vec[i][j];
   int c=m*n;
    for(int i=0;i<m;i++)
         for(int j=0;j<n;j++)
             if(vec[i][j]==0||vec[i][j]==1&&j+1<n&&vec[i][j+1]==1||vec[i][j]==1&&i+1<m&&vec[i+1][j]==1)  c--;
    cout<< c<<endl;
    return 0;
}

发表于 2018-07-19 15:05:36 回复(0)

尼古拉斯凯

import java.util.Scanner;
public class Demo1 { static int row,column; static int array[][]; public static void main(String args[]) {
        Scanner sc = new Scanner(System.in); row = sc.nextInt(); column = sc.nextInt(); array = new int[row][column]; for(int i=0;i<row;i++){ for(int j=0;j<column;j++){ array[i][j] = sc.nextInt();
            }
        } int blocks = findBlocks(array);
        System.out.println(blocks);
    } public static int findBlocks(int array[][]){ int count=0; for(int i=0;i<row;i++){ for(int j=0;j<column;j++){ if(i==0&&j==0&&array[i][j]==1){
                    count++;
                }else if(i>0&&j==0&&array[i-1][j]==0&&array[i][j]==1){
                    count++;
                }else if(i==0&&j>=0&&array[i][j-1]==0&&array[i][j]==1){
                    count++;
                }else if(i>0&&j>0&&array[i-1][j]==0&&array[i][j-1]==0&&array[i][j]==1) {
                    count++;
                }
            }
        } return count;
    }
}

发表于 2018-07-30 21:06:55 回复(1)

花言不知梦

岛屿问题

可以DFS（递归）、或者BFS（队列）来实现

发表于 2020-07-22 00:19:29 回复(0)

ID84848484

void dfs(int r,int c){

if(arr[r-1][c]==1){arr[r-1][c]=0;dfs(r-1,c);}

if(arr[r+1][c]==1){arr[r+1][c]=0;dfs(r+1,c);}

if(arr[r][c-1]==1){arr[r][c-1]=0;dfs(r,c-1);}

if(arr[r][c+1]==1){arr[r][c+1]=0;dfs(r,c+1);}

}

for(int I=1;i<=row;i++){

for(int j=1;j<=col;j++){

if(arr[i][j]){ret++;dfs(I,j);}

发表于 2019-04-11 00:28:14 回复(1)

小白一枚吧

岛屿问题，leetcode 200

发表于 2022-09-07 20:45:03 回复(0)

干饭人🍉

//宽搜或并查集都可解决 这里用宽搜
import java.util.LinkedList;
import java.util.Queue;

public class Base{
    public static void main(String[] args) {
        int[][] map = {
                {1,1,0,0,1},
                {1,0,0,1,0},
                {1,1,0,1,0},
                {0,0,1,0,0}
        };
        boolean[][] vis = new boolean[map.length][map[0].length];
        int res = bfs(map,vis);
        System.out.println(res);
    }
    static class Point{
        int x,y;
        public Point(int x,int y){
            this.x = x;
            this.y = y;
        }
    }
    private static int bfs(int[][] map, boolean[][] vis) {
        int res = 0;
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                if(!vis[i][j] && map[i][j] == 1){
                    res++;
                    Queue<Point> queue = new LinkedList<>();
                    queue.offer(new Point(i,j));
                    while(!queue.isEmpty()){
                        Point point = queue.poll();
                        vis[point.x][point.y] = true;
                        int[] dx = {0,0,-1,1};
                        int[] dy = {1,-1,0,0};
                        for (int k = 0; k < 4; k++) {
                            int x = dy[k] + point.x;
                            int y = dx[k] + point.y;
                            if(x >= 0 && x < map.length &&
                                y >= 0 && y < map[0].length && !vis[x][y] && map[x][y] == 1){
                                queue.offer(new Point(x,y));
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
}

发表于 2022-04-26 01:40:21 回复(0)

HardReset

循环：

找到为 1 的位置，就进行DFS，遍历与这个 1 相连的位置，如果为 1 则设为 0 。

DFS完，结果加 1，继续循环，直到遍历完所有元素。

发表于 2021-04-28 18:54:44 回复(0)

Mark_子奇

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;


int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void dfs(int i, int j, vector<vector<int>>& g, vector<vector<bool>>& visited) {
    if (g[i][j] == 0) {
        return;
    }
    visited[i][j] = true;
    int n = g.size();
    int m = g[0].size();
    for (int k = 0; k < 4; k++) {
        int x = dx[k] + i;
        int y = dy[k] + j;
        if (x >= 0 && x < n && y >= 0 && y < m) {
            if (!visited[x][y] && g[x][y] == 1) {
                dfs(x, y, g, visited);
            }
        }
    }
}


int main() {
    vector<vector<int>> g({
        {1, 1, 0, 0, 1},
        {1, 0, 0, 1, 0},
        {1, 1, 0, 1, 0},
        {0, 1, 1, 0, 0},
        });

    int n = g.size();
    int m = g[0].size();
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && g[i][j] == 1) {
                dfs(i, j, g, visited);
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

编辑于 2020-07-22 15:42:23 回复(0)

叮叮sucess

def find_one(i, j, lst):

    dlt_number = 0
    if i > 0 :
        if lst[i-1][j] == 1:
            dlt_number += 1
    if i < len(lst) - 1:
        if lst[i+1][j] == 1:
            dlt_number += 1
    if j > 0:
        if lst[i][j-1] == 1:
            dlt_number += 1
    if j < len(lst[i]) - 1:
        if lst[i][j+1] == 1:
            dlt_number += 1
    return dlt_number


def number_one(lst):
    res = 0
    location = list()
    temp = 0
    for i in range(len(lst)):
        for j in range(len(lst[i])):
            if lst[i][j] == 1:
                res += 1
                location.append([i,j])
    for loc in location:
        temp += find_one(loc[0], loc[1], lst)
    return (res - temp//2)

a = [[1,1,0,0,1],[1,0,0,1,0],[1,1,0,1,0],[0,0,1,0,0]]
print(number_one(a))

发表于 2020-07-21 22:30:35 回复(0)

辣椒爱吃辣

 public static int test(int[][] sum) { int a = 0;  for (int i = 0; i < sum.length; i++) { for (int j = 0; j < sum[0].length; j++) { if (sum[i][j] == 1) {
                    a++;  } if (i > 0 && i < sum.length - 1 && j > 0 && j < sum[0].length - 1 && sum[i][j] == 1 && (sum[i - 1][j] == 1 || sum[i + 1][j] == 1 || sum[i][j + 1] == 1 || sum[i][j - 1] == 1)) {
                    a--;  } //                if ((i == 0 || i == sum.length - 1) && j > 0 && j < sum[0].length - 1 && sum[i][j] == 1 && (sum[i][j + 1] == 1 || sum[i][j - 1] == 1)) { //                    a--; //                }  if ((j == 0 || j == sum[0].length - 1) && i > 0 && i < sum.length - 1 && sum[i][j] == 1 &&(sum[i - 1][j] == 1 || sum[i + 1][j] == 1)) {
                    a--;  }
            }
        } return a;  }

发表于 2019-08-28 17:20:41 回复(0)

王小刷子

    public static int findOneBlock(int[][] array){
        if (array == null || array.length == 0) {
            return 0;
        }
        int row = array.length;
        int col = array[0].length;
        //假设初始所有的数都是一个单独的1块，逐步剔除不符合要求的
        int count = row * col;
        //剔除0元素
        //剔除上边或左边挨着1的元素（换言之，这个元素只有上边和左边都不是1，才能说明它是一个“1数字块”的开始）
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (array[i][j] == 0 || i > 0 && array[i - 1][j] == 1 || j > 0 && array[i][j - 1] == 1) {
                    count--;
                }
            }
        }
        return count;
    }

发表于 2018-07-26 22:55:06 回复(3)

#229

public int groupCount(int[][] matrix) {
    int count = 0;
    for(int i=0;i<matrix.length;i++){
         for(int j=0;j<matrix[0].length;j++){
             if(i==0 && j==0 || i==0 && matrix[j-1]==0 || j==0 && matrix[i-1]==0 || matrix[i-1]==0 && matrix[j-1]==0) count++;
        }
    }
    return count;
}

发表于 2018-07-24 23:50:33 回复(2)

安之若素201803230757677

void dfs(std::vector<std::vector<int> >a,size_t i,size_t j){
a[i][j] = 2;
if(i>a.size()-1 && j > a[0].size()-1){
return;
}
if(i<a.size()-1 && a[i+1][j] == 1){
dfs(a,i+1,j);
}
if(j<a[0].size()-1 && a[i][j+1] == 1){
//向右
dfs(a,i,j+1);
}
if(i >0 && a[i-1][j] == 1){
dfs(a,i-1,j);
}
if(j>0 && a[i][j-1] == 1){
dfs(a,i,j-1);
}
}

int countofgrid(std::vector<std::vector<int> > a){

int row = a.size();
int col = a[0].size();
if(row == 0 || col == 0){
return 0;
}
int i = 0;
int j = 0;
int count = 0;
for(i=0;i<row;i++){
for(j=0;j<col;j++){
if(a[i][j] == 1){
count++;
dfs(a,i,j);
}
}
}
return count;
}

发表于 2018-07-24 17:38:39 回复(0)

【编程题】一个只包含0和1的阵列，找到1的组的个数，每个组的

问题信息

热门推荐

相关试题