统计矩阵中按递增顺序的数字个数

huangapple go评论107阅读模式
英文:

Count number of ones in a matrix in increasing order

问题

  1. public class Islands {
  2. // No of rows and columns
  3. static final int ROW = 4, COL = 5;
  4. // A function to check if a given cell (row, col) can
  5. // be included in DFS
  6. static boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
  7. // row number is in range, column number is in range
  8. // and value is 1 and not yet visited
  9. return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
  10. }
  11. // A utility function to do DFS for a 2D boolean matrix.
  12. // It only considers the 8 neighbors as adjacent vertices
  13. static void DFS(int M[][], int row, int col, boolean visited[][]) {
  14. // These arrays are used to get row and column numbers
  15. // of 8 neighbors of a given cell
  16. int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
  17. int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
  18. // Mark this cell as visited
  19. visited[row][col] = true;
  20. // Recur for all connected neighbours
  21. for (int k = 0; k < 8; ++k)
  22. if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
  23. DFS(M, row + rowNbr[k], col + colNbr[k], visited);
  24. }
  25. // The main function that returns count of islands in a given
  26. // boolean 2D matrix
  27. static int countIslands(int M[][]) {
  28. // Make a bool array to mark visited cells.
  29. // Initially all cells are unvisited
  30. boolean visited[][] = new boolean[ROW][COL];
  31. // Initialize count as 0 and traverse through all the cells
  32. // of the given matrix
  33. int count = 0;
  34. for (int i = 0; i < ROW; ++i)
  35. for (int j = 0; j < COL; ++j)
  36. if (M[i][j] == 1 && !visited[i][j]) // If a cell with
  37. { // value 1 is not
  38. // visited yet, then a new island is found. Visit all
  39. // cells in this island and increment island count
  40. DFS(M, i, j, visited);
  41. ++count;
  42. }
  43. return count;
  44. }
  45. // Driver method
  46. public static void main(String[] args) throws java.lang.Exception {
  47. int M[][] = new int[][] { { 1, 0, 0, 1, 0 }, { 1, 0, 1, 0, 0 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1 } };
  48. System.out.println("Number of islands is: " + countIslands(M));
  49. }
  50. }
英文:

I have this island program that just displays the number of possible islands in a matrix.

I have a matrix of 1's and 0's I want to get group of 1's in row wise, column wise and diagonal wise. This program count the number of possibilities and returns 5 as output for below input.

  1. { 1, 0, 0, 1, 0 },
  2. { 1, 0, 1, 0, 0 },
  3. { 0, 0, 1, 0, 1 },
  4. { 1, 0, 1, 0, 1 }

But I need output as island sizes in increasing order as 1 2 2 4

How to achieve this?

Explanation: a) last row first column has single island, b) first row 1st column, 2nd row 1st column and has island of size 2. c) 3rd row last column, last row last column has island of size 2. d) 1st row 4th column, remaining rows 3rd column has size of 4.

  1. public class Islands {
  2. // No of rows and columns
  3. static final int ROW = 4, COL = 5;
  4. // A function to check if a given cell (row, col) can
  5. // be included in DFS
  6. static boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
  7. // row number is in range, column number is in range
  8. // and value is 1 and not yet visited
  9. return (row &gt;= 0) &amp;&amp; (row &lt; ROW) &amp;&amp; (col &gt;= 0) &amp;&amp; (col &lt; COL) &amp;&amp; (M[row][col] == 1 &amp;&amp; !visited[row][col]);
  10. }
  11. // A utility function to do DFS for a 2D boolean matrix.
  12. // It only considers the 8 neighbors as adjacent vertices
  13. static void DFS(int M[][], int row, int col, boolean visited[][]) {
  14. // These arrays are used to get row and column numbers
  15. // of 8 neighbors of a given cell
  16. int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
  17. int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
  18. // Mark this cell as visited
  19. visited[row][col] = true;
  20. // Recur for all connected neighbours
  21. for (int k = 0; k &lt; 8; ++k)
  22. if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
  23. DFS(M, row + rowNbr[k], col + colNbr[k], visited);
  24. }
  25. // The main function that returns count of islands in a given
  26. // boolean 2D matrix
  27. static int countIslands(int M[][]) {
  28. // Make a bool array to mark visited cells.
  29. // Initially all cells are unvisited
  30. boolean visited[][] = new boolean[ROW][COL];
  31. // Initialize count as 0 and travese through the all cells
  32. // of given matrix
  33. int count = 0;
  34. for (int i = 0; i &lt; ROW; ++i)
  35. for (int j = 0; j &lt; COL; ++j)
  36. if (M[i][j] == 1 &amp;&amp; !visited[i][j]) // If a cell with
  37. { // value 1 is not
  38. // visited yet, then new island found, Visit all
  39. // cells in this island and increment island count
  40. DFS(M, i, j, visited);
  41. ++count;
  42. }
  43. return count;
  44. }
  45. // Driver method
  46. public static void main(String[] args) throws java.lang.Exception {
  47. int M[][] = new int[][] { { 1, 0, 0, 1, 0 }, { 1, 0, 1, 0, 0 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1 } };
  48. System.out.println(&quot;Number of islands is: &quot; + countIslands(M));
  49. }
  50. }

答案1

得分: 1

对代码进行以下更改以解决问题:

  • 添加静态变量size,用于计算每个岛屿的大小。
  • count替换为listSizes,用于存储每个岛屿的大小。将新岛屿的大小添加到此列表中。
  • 调用方法(从countIslands重命名为sizeIslands)以获取最终的listSizes
  • 在打印列表之前对其进行排序。

最终代码:

  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.List;
  4. public class Islands {
  5. // 行和列的数量
  6. static final int ROW = 4, COL = 5;
  7. static int size;
  8. // 一个函数,用于检查给定的单元格(行、列)是否可以包含在DFS中
  9. static boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
  10. // 行号在范围内,列号在范围内
  11. // 值为1且尚未被访问
  12. return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
  13. }
  14. // 用于执行2D布尔矩阵的DFS的实用函数。
  15. // 它只将8个相邻的单元格视为相邻的顶点
  16. static void DFS(int M[][], int row, int col, boolean visited[][]) {
  17. // 这些数组用于获取给定单元格的8个相邻单元格的行号和列号
  18. int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
  19. int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
  20. // 将此单元格标记为已访问
  21. visited[row][col] = true;
  22. size++;
  23. // 递归访问所有相邻的邻居
  24. for (int k = 0; k < 8; ++k)
  25. if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
  26. DFS(M, row + rowNbr[k], col + colNbr[k], visited);
  27. }
  28. // 返回给定布尔2D矩阵中各个岛屿的大小的主要函数
  29. static List<Integer> sizeIslands(int M[][]) {
  30. // 创建一个布尔数组以标记已访问的单元格。
  31. // 最初所有单元格都未被访问
  32. boolean visited[][] = new boolean[ROW][COL];
  33. // 初始化空列表,并遍历给定矩阵的所有单元格
  34. List<Integer> listSizes = new ArrayList<Integer>();
  35. for (int i = 0; i < ROW; ++i)
  36. for (int j = 0; j < COL; ++j)
  37. if (M[i][j] == 1 && !visited[i][j]) // 如果值为1的单元格尚未被访问
  38. {
  39. // 则找到新的岛屿,访问此岛屿中的所有单元格并增加岛屿大小
  40. size = 0;
  41. DFS(M, i, j, visited);
  42. listSizes.add(size);
  43. }
  44. return listSizes;
  45. }
  46. // 主方法
  47. public static void main(String[] args) throws java.lang.Exception {
  48. int M[][] = new int[][] { { 1, 0, 0, 1, 0 }, { 1, 0, 1, 0, 0 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1 } };
  49. List<Integer> list = sizeIslands(M);
  50. Collections.sort(list);
  51. System.out.println("Sizes of islands are: " + list);
  52. }
  53. }
英文:

Make following changes to solve it:

  • Add static variable size to count size for each island.
  • Replace count by listSizes to store the size of each island. New island's size is added to this list.
  • Invoke the method (renamed from countIslands to sizeIslands) to get final listSizes.
  • Sort the list before printing it out.

Final code:

  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.List;
  4. public class Islands {
  5. // No of rows and columns
  6. static final int ROW = 4, COL = 5;
  7. static int size;
  8. // A function to check if a given cell (row, col) can
  9. // be included in DFS
  10. static boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
  11. // row number is in range, column number is in range
  12. // and value is 1 and not yet visited
  13. return (row &gt;= 0) &amp;&amp; (row &lt; ROW) &amp;&amp; (col &gt;= 0) &amp;&amp; (col &lt; COL) &amp;&amp; (M[row][col] == 1 &amp;&amp; !visited[row][col]);
  14. }
  15. // A utility function to do DFS for a 2D boolean matrix.
  16. // It only considers the 8 neighbors as adjacent vertices
  17. static void DFS(int M[][], int row, int col, boolean visited[][]) {
  18. // These arrays are used to get row and column numbers
  19. // of 8 neighbors of a given cell
  20. int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
  21. int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
  22. // Mark this cell as visited
  23. visited[row][col] = true;
  24. size++;
  25. // Recur for all connected neighbours
  26. for (int k = 0; k &lt; 8; ++k)
  27. if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
  28. DFS(M, row + rowNbr[k], col + colNbr[k], visited);
  29. }
  30. // The main function that returns size of islands in a given
  31. // boolean 2D matrix
  32. static List&lt;Integer&gt; sizeIslands(int M[][]) {
  33. // Make a bool array to mark visited cells.
  34. // Initially all cells are unvisited
  35. boolean visited[][] = new boolean[ROW][COL];
  36. // Initialize empty list and travese through the all cells
  37. // of given matrix
  38. List&lt;Integer&gt; listSizes = new ArrayList&lt;Integer&gt;();
  39. for (int i = 0; i &lt; ROW; ++i)
  40. for (int j = 0; j &lt; COL; ++j)
  41. if (M[i][j] == 1 &amp;&amp; !visited[i][j]) // If a cell with
  42. { // value 1 is not
  43. // visited yet, then new island found, Visit all
  44. // cells in this island and increment island count
  45. size = 0;
  46. DFS(M, i, j, visited);
  47. listSizes.add(size);
  48. }
  49. return listSizes;
  50. }
  51. // Driver method
  52. public static void main(String[] args) throws java.lang.Exception {
  53. int M[][] = new int[][] { { 1, 0, 0, 1, 0 }, { 1, 0, 1, 0, 0 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1 } };
  54. List&lt;Integer&gt; list = sizeIslands(M);
  55. Collections.sort(list);
  56. System.out.println(&quot;Sizes of islands are: &quot; + list);
  57. }

huangapple
  • 本文由 发表于 2020年8月30日 00:25:41
  • 转载请务必保留本文链接:https://go.coder-hub.com/63649277.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定