Problem : Given a matrix of 0 and 1s. Find all the possible holes and return an array with hole sizes.
All adjacent 1's are part of 1 hole as long as they are left,right, up and down to each other. diagonal 1's do not matter.
Example 1 : {1,0,1,1},
Example 2 : {1,1,1,1},
{0,0,1,1},
{1,0,1,1},
{0,1,0,0},
{1,1,0,1}
Result : {1,6,1,3,1}Example 2 : {1,1,1,1},
{1,1,1,1},
{1,1,1,1},
{1,1,0,0},
{1,1,0,1}
Result : {16, 1}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | public int[] findHoles(int[][] input){ int [] results = new int[input.length *2]; //initialize a temp array to maintain state and set all states to 0 //0 = unvisited, 1 = visited. int total =0; int[][]temp = new int[input.length][input[0].length]; for(int i=0; i < temp.length; i++){ for(int j=0; j < temp[i].length; j++){ temp[i][j]=0; } } Stack stack = new Stack(); for(int i=0; i < input.length; i++){ for(int j=0; j < input[i].length; j++){ if(input[i][j]==1 && temp[i][j] ==0){ temp[i][j] = 1; int count =1; int [] neighbour = new int[] {i,j}; if(neighbour[0] != -1){ stack.push(neighbour); } while(neighbour[0] != -1 || !stack.isEmpty()){ if(neighbour[0] != -1){ neighbour = getNeighbour(neighbour[0],neighbour[1],input, temp); if(neighbour[0] != -1){ stack.push(neighbour); count++; } }else{ neighbour = (int[])stack.pop(); neighbour= getNeighbour(neighbour[0],neighbour[1],input, temp); if(neighbour[0] != -1){ stack.push(neighbour); count++; } } } results[total] =count; total++; } } } return results; } public int[] getNeighbour(int i, int j, int[][] input, int[][] temp){ //check for last element by checking "j < input[i].length -1" int [] result = new int[2]; //check right if(j < input[i].length -1 && input[i][j+1] ==1 && temp[i][j+1]==0){ temp[i][j+1] =1; result[0]=i; result[1]= j+1; return result; }//check right else if(j > 0 && input[i][j-1] ==1 && temp[i][j-1]==0){ temp[i][j-1] =1; result[0]=i; result[1]= j-1; return result; }//check up else if(i>0 && input[i-1][j] ==1 && temp[i-1][j]==0){ temp[i-1][j] =1; result[0]=i-1; result[1]= j; return result; }//check down else if(i< input.length -1 && input[i+1][j] ==1 && temp[i+1][j]==0){ temp[i+1][j] =1; result[0]=i+1; result[1]= j; return result; } //if no neighbor then return -1,-1 result[0]=-1; result[1]= -1; return result; } |
No comments:
Post a Comment