首页 > 试题广场 >

连通块

[编程题]连通块

热度指数：337 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右）判断岛屿个数。

输入描述:

第一行输入两个数字n，m（1<=n<=200，1<=m<=200）
后面n行01序列，每一行m个字符，表示陆地和海洋

输出描述:

输出一个数字表示岛屿的个数

示例1

输入

输出

算法知识视频讲解

牛客355357号

#include <iostream>
(720)#include <vector>


using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;


/*
1 0 1 0 0 1
0 1 1 1 0 1
1 0 1 0 0 1
 */

void inflate(vvi& raw,vvi&visit,int x,int y){
    int m = raw.size() -1,n = raw[0].size() -1;
    if(x> m|| y>n)
        return;
    if(x<0 || y<0)
        return;
    if(visit[x][y] == 1)
        return;
    visit[x][y] =1;
    if(raw [x][y] != 1)
        return;
    inflate(raw ,visit,x+1,y);
    inflate(raw ,visit,x-1,y);
    inflate(raw ,visit,x,y+1);
    inflate(raw ,visit,x,y-1);
}



int main() {
    int m, n;

    while (cin >> m >> n) {
        vvi raw(m,vi(n,0));
        vvi visit(m,vi(n,0));

        /*
          1 0 1
          1 1 0
          0 0 1
        */

        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                cin >> raw[i][j];
            }
        auto cnt = 0;
        for (int i= 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if(visit[i][j] == 0 && raw[i][j] ==1){
                    inflate(raw,visit,i,j);
                    cnt++;
                }
            }
        }
        cout<<cnt<<endl;
    }
    return 0;

}

本地測沒問題啊

发表于 2020-03-01 17:15:46 回复(0)

XTher

过是过了，就是写麻烦了。

#include <bits/stdc++.h>
using namespace std;

int dir[4][2] = 
{
    {0, 1},
    {0, -1},
    {-1, 0},
    {1, 0}
};
char sz[205][205];
int visit[205][205];
int n, m, ans;

int judge(int i, int j)
{
	if (i < 0 || i >= n || j < 0 || j >= m)
	{
		return 0;
	}
	if (sz[i][j] == '1' && visit[i][j] == 0)
	{
		return 1;
	}
	return 0;
}

void dfs(int i, int j)
{
	visit[i][j] = 1;
	for (int a = 0; a < 4; ++a)
	{
		bool pd = judge(i + dir[a][0], j + dir[a][1]);
		if (pd)
		{
			visit[i + dir[a][0]][j + dir[a][1]] = 1;
			dfs(i + dir[a][0], j + dir[a][1]);
		}
	}
}

int main()
{
    // DFS
    ios::sync_with_stdio(false);
    cin >> n >> m;
    memset(sz, 0, sizeof(sz));
    memset(visit, 0, sizeof(visit));
    ans = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> sz[i][j];
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
        	if (sz[i][j] == '1' && visit[i][j] == 0)
        	{
				dfs(i, j);
				ans++;
			}
        }
    }
    cout << ans;
    return 0;
}

发表于 2020-02-24 12:12:38 回复(0)

牛客385628756号

import java.util.Scanner;
import java.util.LinkedList;
public class Main{
private static LinkedList<Point> points = new LinkedList();
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int row = sc.nextInt();
int col = sc.nextInt();
char[][] map = new char[row][col];
for(int i=0;i<row;i++){
String str = sc.next();
char[] chars = str.toCharArray();
map[i] = chars;
}
boolean[][] flags = new boolean[row][col];
int num = findIslandNum(map,flags);
System.out.println(num);
}
private static int findIslandNum(char[][] map,boolean[][] flags){
int num=0;
for(int i=0;i<map.length;i++){
for(int j=0;j<map[0].length;j++){
if(map[i][j]=='1'&&flags[i][j]==false){
num++;
flags[i][j] = true;
points.add(new Point(i,j));
while(!points.isEmpty()){
Point p = points.pollFirst();
int x = p.x;
int y = p.y;
if(x-1>=0&&x-1<map.length&&map[x-1][y]=='1'&&flags[x-1][y]==false){
points.add(new Point(x-1,y));
flags[x-1][y]=true;
}
if(x+1>=0&&x+1<map.length&&map[x+1][y]=='1'&&flags[x+1][y]==false){
points.add(new Point(x+1,y));
flags[x+1][y]=true;
}
if(y-1>=0&&y-1<map[0].length&&map[x][y-1]=='1'&&flags[x][y-1]==false){
points.add(new Point(x,y-1));
flags[x][y-1]=true;
}
if(y+1>=0&&y+1<map[0].length&&map[x][y+1]=='1'&&flags[x][y+1]==false){
points.add(new Point(x,y+1));
flags[x][y+1]=true;
}
}
}
}
}
return num;
}
}
class Point{
public int x;
public int y;
public Point(int x,int y){
this.x = x;
this.y = y;
}
}

发表于 2021-04-21 10:09:06 回复(0)

灰原哀·

import java.util.*;
public class Main {
    static int xx = 1;
    static int n, m;
    static Queue<a>  queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();
        int[][] ans = new int[n][m];
        for(int i = 0; i < n; i++){
            String str = scanner.next();
            for(int j = 0; j < m; j++){
                ans[i][j] = str.charAt(j) == '1' ? 1 : 0;
            }
        }
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(ans[i][j] == 1){
                    queue.add(new a(i, j));
                    ans[i][j] = ++xx;
                    bfs(i, j, ans);
                }
            }
        }
//        for(int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                System.out.printf("%d", ans[i][j]);
//            }
//            System.out.println();
//        }
        System.out.println(--xx);
    }

    public static void  bfs(int x, int y, int[][] ans){
        int[][] fx = {{1,0}, {0,1}, {0,-1},{-1,0}};
        while (!queue.isEmpty()){
            for(int i = 0; i < 4; i++){
                int bx = fx[i][0] + queue.element().x;
                int by = fx[i][1] + queue.element().y;
                if(bx >= 0 && bx < n && by >=0 && by < m && ans[bx][by] == 1){
                    ans[bx][by] = xx;
                    queue.add(new a(bx, by));
                }
            }
            queue.remove();
        }
    }
}
class a{
    public int x;
    public int y;
    public a(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

发表于 2022-06-30 12:02:06 回复(0)

牛客729047582号

#include<iostream>
#include<vector>
using namespace std;
void dfs(vector<vector<char>>& grid,int i,int j){
grid[i][j]='0';
if(i-1>=0&&grid[i-1][j]=='1')
dfs(grid,i-1,j);
if(i+1<grid.size()&&grid[i+1][j]=='1')
dfs(grid,i+1,j);
if(j-1>=0&&grid[i][j-1]=='1')
dfs(grid,i,j-1);
if(j+1<grid[0].size()&&grid[i][j+1]=='1')
dfs(grid,i,j+1);
}
int main(){
int n,m;
cin>>n>>m;
vector<vector<char>> grid(n,vector<char>(m));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>grid[i][j];
}
}
int lands=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]=='1'){
lands++;
dfs(grid,i,j);
}
}
}
cout<<lands<<endl;
return 0;
}

发表于 2021-09-10 19:14:11 回复(0)

oliver.chen

import java.util.*;

public class Main {
    static int n,m;
    static int[][] map;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        map = new int[201][201];
        for (int i = 0; i < n; i++){
            String input = in.next();
            char[] chars = input.toCharArray();
            for (int j = 0; j < m ; j++){
                map[i][j] = (int)chars[j] - 48 ;
            }
        }
        int count = 0;
        int[][] dp = new int[201][201];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (map[i][j] == 1 && dp[i][j] != 1){
                    visit1(dp, i, j);
                    count++;
                }
            }
        }
        System.out.println(count);
    }
    static void visit1(int[][] dp, int i,int j){
        LinkedList<Point> points = new LinkedList<>();
        points.offer(new Point(i,j));
        while (!points.isEmpty()){
            Point first = points.getFirst();
            int x = first.x;
            int y = first.y;
            if (map[x][y] == 1 && dp[x][y] == 0){
                dp[x][y] = 1;
                if (x - 1 >= 0 && dp[x - 1][y] != 1 && map[x - 1][y] == 1)
                    points.offer(new Point(x - 1,y));
                if (x + 1 < n && dp[x + 1][y] != 1 && map[x + 1][y] == 1)
                    points.offer(new Point(x + 1,y));
                if (y - 1 >= 0 && dp[x][y - 1] != 1 && map[x][y - 1] == 1)
                    points.offer(new Point(x,y - 1));
                if (y + 1 < m && dp[x][y + 1] != 1 && map[x][y + 1] == 1)
                    points.offer(new Point(x,y + 1));
            }
            points.removeFirst();
        }
    }
}
class Point{
    int x,y;
    Point(){

    }
    Point(int x,int y){
        this.x = x;
        this.y = y;
    }
}

发表于 2020-11-07 20:47:20 回复(0)

Java

格拉摩根键圣

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] lines = sc.nextLine().split(" ");
        int m = Integer.parseInt(lines[0]);
        int n = Integer.parseInt(lines[1]);
        if(n < 1 || n > 200 || m < 1 || m > 200){
            //System.out.println(0);
            return;
        }
        int[][] arr = new int[m][n];
        int r = 0;
        while(sc.hasNext()){
            String line = sc.nextLine();
            for(int j = 0;j < n;j++){
                arr[r][j] = line.charAt(j) - '0';
            }
            r++;
            if(r >= m){
                break;
            }
        }
        if(m == 0 || n == 0){
            System.out.println(0);
            return;
        }
        int cnt = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(arr[i][j] == 1){
                    cnt++;
                    dfs(arr,i,j);
                }
            }
        }
        System.out.println(cnt);

    }

    private static void dfs(int[][] arr,int r,int c){
        int m = arr.length;
        int n = arr[0].length;
        if(r < 0 || c < 0 || r >= m || c >= n || arr[r][c] == 0){
            return;
        }
        arr[r][c] = 0;
        dfs(arr,r + 1,c);
        dfs(arr,r - 1,c);
        dfs(arr,r,c + 1);
        dfs(arr,r,c - 1);
    }
}

本地调试是没问题的，leetcode也过了，牛客只有93.75说数组越界，感觉问题出在输入上了但不知道为什么和怎么改，求大神解答

发表于 2020-02-29 17:54:53 回复(0)

YN-HUAI

import java.util.Scanner;

public class Main {
    private static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        int n = Integer.parseInt(line.split(" ")[0]);
        int m = Integer.parseInt(line.split(" ")[1]);
        if(n<1||n>200||m<1||m>200){
            return;
        }
        int[][] numbers = new int[n][m];
        boolean[][] isVisited = new boolean[n][m];
        int row = 0;
        while (sc.hasNext()) {
            line = sc.nextLine();
            String[] num = line.split("");
            for (int i = 0; i < m; i++) {
                numbers[row][i] = Integer.parseInt(num[i]);
            }
            row++;
           if (row == n) {
                break;
            }

        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (numbers[i][j] == 1 && !isVisited[i][j]) {
                    count += 1;
                    dfs(numbers, isVisited, i, j);
                }
            }
        }

        System.out.println(count);
        
    }

private static void dfs(int[][] numbers, boolean[][] isVisited, int row, int col) {
       if (row >= 0 && row < numbers.length && col >= 0 && col < numbers[0].length) {
            if (numbers[row][col] == 1 && !isVisited[row][col]) {
                isVisited[row][col] = true;
                dfs(numbers, isVisited, row - 1, col);
                dfs(numbers, isVisited, row + 1, col);
                dfs(numbers, isVisited, row, col - 1);
                dfs(numbers, isVisited, row, col + 1);
            }

        }
    }


}

通过率93.7，说有数组越界，不知道问题出在哪

发表于 2020-02-26 23:44:25 回复(0)

我来自哪里

python 代码写的通过了56.72，不是很明白，测试是对的

row_col = input()
row, col = int(row_col.split(" ")[0]), int(row_col.split(" ")[1])
list_number = []
zeros_array = []
for i in range(int(row)):
    row_content = input()
    list_number.append([int(c) for c in row_content])
    zeros_array.append([0 for c in range(col)])

count = 2

land_number = 0
#随机抽取一个数字
list_array = []
for i in range(row):
    for j in range(col):
        count_1 = 0
        count_2 = 0
        count_3 = 0
        count_4 = 0
        if zeros_array[i][j] == 0 and list_number[i][j] == 1:
            zeros_array[i][j] = 10
            if i + 1 < row:
                if zeros_array[i + 1][j] == 0:
                    count_1 = 0
                    if list_number[i + 1][j] == 1:
                        zeros_array[i + 1][j] = 10
                else:
                    count_1 = 1
            if i - 1 > -1:
                if zeros_array[i - 1][j] == 0:
                    count_2 = 0
                    if list_number[i - 1][j] == 1:
                        zeros_array[i - 1][j] = 10
                else:
                    count_2 = 1
            if j + 1 < col:
                if zeros_array[i][j + 1] == 0:
                    count_3 = 0
                    if list_number[i][j + 1] == 1:
                        zeros_array[i][j + 1] = 10
                else:
                    count_3 = 1
            if j - 1 > -1:
                if zeros_array[i][j - 1] == 0:
                    count_4 = 0
                    if list_number[i][j - 1] == 1:
                        zeros_array[i][j - 1] = 10
                else:
                    count_4 = 1
            if count_1 == 0 and count_2 == 0 and count_3 == 0 and count_4 == 0:
                land_number += 1


print(land_number)

发表于 2020-02-26 15:46:46 回复(0)