【编程题】一个只包含0和1的阵列,找到1的组的个数,每个组的定义是横向和纵向相邻的值都为1,如图中一共有4个组,用不同颜色的框分割(可以参见不同粗细勾画起来的框)。
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); }
#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; }
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; } }
//宽搜或并查集都可解决 这里用宽搜 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; } }
#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; }
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))
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; }