fork(2) download
copy 
  1. import java.util.ArrayList;
  2.  
  3. class RectangularIslands {
  4.  
  5. 	/*
  6. Count number of islands where every island is row-wise and column-wise separated
  7. Given a rectangular matrix which has only two possible values ‘X’ and ‘O’. The values ‘X’ always appear in form of rectangular islands and these islands are always row-wise and column-wise separated by at least one line of ‘O’s. Note that islands can only be diagonally adjacent. Count the number of islands in the given matrix.
  8.  
  9. Examples:
  10.  
  11. mat[M][N] =  {{'O', 'O', 'O'},
  12.               {'X', 'X', 'O'},
  13.               {'X', 'X', 'O'},
  14.               {'O', 'O', 'X'},
  15.               {'O', 'O', 'X'},
  16.               {'X', 'X', 'O'}
  17.              };
  18. Output: Number of islands is 3
  19.  
  20. mat[M][N] =  {{'X', 'O', 'O', 'O', 'O', 'O'},
  21.               {'X', 'O', 'X', 'X', 'X', 'X'},
  22.               {'O', 'O', 'O', 'O', 'O', 'O'},
  23.               {'X', 'X', 'X', 'O', 'X', 'X'},
  24.               {'X', 'X', 'X', 'O', 'X', 'X'},
  25.               {'O', 'O', 'O', 'O', 'X', 'X'},
  26.              };
  27. Output: Number of islands is 4
  28. 	 */
  29. 	public static void main(String[] args) {
  30. 		char[][] mat1   =  
  31. 		     {{'O', 'O', 'O'},
  32.              {'X', 'X', 'O'},
  33.              {'X', 'X', 'O'},
  34.              {'O', 'O', 'X'},
  35.              {'O', 'O', 'X'},
  36.              {'X', 'X', 'O'}
  37.             };
  38. 	findIslands(mat1);
  39.  
  40. 		char[][] mat2 =  
  41. 			     {{'X', 'O', 'O', 'O', 'O', 'O'},
  42. 	              {'X', 'O', 'X', 'X', 'X', 'X'},
  43. 	              {'O', 'O', 'O', 'O', 'O', 'O'},
  44. 	              {'X', 'X', 'X', 'O', 'X', 'X'},
  45. 	              {'X', 'X', 'X', 'O', 'X', 'X'},
  46. 	              {'O', 'O', 'O', 'O', 'X', 'X'},
  47. 	             };
  48. 		findIslands(mat2);
  49.  
  50. 		char[][] mat3 =
  51. 				  {{'X', 'O', 'O', 'O', 'O', 'O'},
  52. 	              {'O', 'O', 'X', 'O', 'X', 'X'},
  53. 	              {'O', 'O', 'O', 'O', 'O', 'O'},
  54. 	              {'X', 'O', 'X', 'O', 'X', 'X'},
  55. 	              {'X', 'O', 'X', 'O', 'X', 'X'},
  56. 	              {'O', 'O', 'O', 'O', 'X', 'X'},
  57. 	             };
  58. 		findIslands(mat3);
  59.  
  60. 		char[][] mat4 =
  61. 			  {{'X', 'X', 'X', 'X', 'X', 'X'},
  62. 			{'X', 'X', 'X', 'X', 'X', 'X'},
  63. 			{'X', 'X', 'X', 'X', 'X', 'X'},
  64. 			{'X', 'X', 'X', 'X', 'X', 'X'},
  65. 			{'X', 'X', 'X', 'X', 'X', 'X'},
  66. 			{'X', 'X', 'X', 'X', 'X', 'X'},
  67.            };
  68. 	findIslands(mat4);
  69.  
  70. 	}
  71.  
  72.  
  73. 	public static ArrayList<RectangularIslands.Island> islandList;
  74. 	public static void findIslands(char[][] matrix) {
  75. 		islandList = new ArrayList<RectangularIslands.Island>();
  76.  
  77. 		int i=0,j=0;
  78. 		int matrixRows = matrix.length;
  79. 		int matrixCols = matrix[0].length;
  80.  
  81. 		while(i<matrixRows){
  82. 			j=0;
  83. 			while(j<matrixCols){
  84. 				if(matrix[i][j] =='X'){
  85. 					// Check if this position is already considered in previously observed island
  86. 					Island notedIsland =  isInIsland(i,j);
  87. 					if(notedIsland!=null){
  88. 						// point is already in noted island. So directly jump to position outside island
  89. 						j=notedIsland.endPointColnum+1;
  90. 					}else{
  91. 						int startPointRownum = i;
  92. 						int startPointColnum = j;
  93. 						j++;
  94. 						// We have found top-left corner of island. Now find the boundaries
  95. 						while(j<matrixCols && matrix[i][j]=='X'){
  96. 							j++; // Keep moving right till we find X or end of matrix
  97. 						}
  98. 						int endPointColnum = j-1; // Current j points to 'O' or matrix boundry
  99.  
  100. 						// Find the bottom of island 
  101. 						int k=i;
  102. 						while(k+1<matrixRows && matrix[k+1][startPointColnum]=='X'){
  103. 							// Keep moving right till we find X or end of matrix
  104. 							k++;
  105. 						}
  106. 						int endPointRownum = k;
  107.  
  108. 						// Create rectangle object and add to list
  109. 						Island ilnd = new Island();
  110. 						ilnd.startPointRownum=startPointRownum;
  111. 						ilnd.startPointColnum=startPointColnum;
  112. 						ilnd.endPointRownum=endPointRownum;
  113. 						ilnd.endPointColnum=endPointColnum;
  114. 						islandList.add(ilnd);
  115. 					}
  116. 				}else{
  117. 					j++;
  118. 				}
  119. 			}
  120. 			i++;
  121. 		}
  122.  
  123. 		System.out.println("No of islands ="+islandList.size());
  124. 	}
  125. 	static private class Island{
  126. 		public int startPointRownum,startPointColnum,endPointRownum,endPointColnum;
  127. 	}
  128.  
  129. 	public static Island isInIsland(int rownum, int colnum){
  130. 		for(Island ilnd:islandList){
  131. 			if(ilnd.startPointRownum<=rownum && ilnd.startPointColnum<=colnum && ilnd.endPointRownum>=rownum && ilnd.endPointColnum>=colnum){
  132. 				return ilnd;
  133. 			}
  134. 		}
  135. 		return null;
  136. 	}
  137.  
  138. }
  139.  
Success #stdin #stdout 0.09s 320320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
No of islands =3
No of islands =4
No of islands =6
No of islands =1
https://ideone.com/IlpH9t
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!