This is my solution if it can help

Question about the task

Rectangle algorithms

Java Core, Level 10, Lesson 10

Under discussion

hope it could help someone

1. Here we have a two-dimensional N*N array that contains several rectangles.
2. The various rectangles do not touch or overlap.
3. The interior of each rectangle is filled with 1s.
4. The array values have the following meaning:
4.1) a[i, j] = 1 if element (i, j) belongs to a rectangle
4.2) a[i, j] = 0, otherwise
5. getRectangleCount must return the number of rectangles.
6. The main method is not tested

Requirements:

The Solution class must have a getRectangleCount method with one byte[][] parameter.
The getRectangleCount method must be public.
The getRectangleCount method must be static.
The getRectangleCount method must return the number of rectangles found in the passed array (in accordance with the task).

package com.codegym.task.task20.task2026; /* Rectangle algorithms */ public class Solution { public static void main(String[] args) { byte[][] a1 = new byte[][]{ {1, 1, 0, 0}, {1, 1, 0, 0}, {1, 1, 0, 0}, {1, 1, 0, 1} }; byte[][] a2 = new byte[][]{ {1, 0, 0, 1}, {0, 0, 0, 0}, {0, 0, 0, 0}, {1, 0, 0, 1} }; int count1 = getRectangleCount(a1); System.out.println("count = " + count1 + ". Must be 2"); int count2 = getRectangleCount(a2); System.out.println("count = " + count2 + ". Must be 4"); } public static int getRectangleCount(byte[][] a) { int count = 0; int startRow = -1; int startColumn = -1; int endRow = -1; int endColumn = -1; int width = -1; int height = -1; for (int i = 0; i < a.length; i++) { for (int j = 0; j < a[i].length; j++) { if (a[i][j] == 0 && (width + 1) > 0) { break; } else if (a[i][j] == 1 && (width + 1) > 0) { width++; endRow = j; endColumn = i; } else if (a[i][j] == 1 && (width + 1) == 0) { if (startRow < 0) { startRow = j; startColumn = i; } width++; endRow = j; endColumn = i; } } if ((width + 1) > 0) { int widthNext = 0; for (int j = startColumn; j < a.length; j++) { for (int k = startRow; k < endRow + 1; k++) { if (a[j][k] == 1) { widthNext++; } else { break; } } if ((width + 1) == widthNext) { for (int k = startRow; k < endRow + 1; k++) { a[endColumn][k] = 0; } height++; endColumn++; widthNext = 0; } else { break; } } count++; i--; } startRow = -1; startColumn = -1; width = -1; height = -1; endRow = -1; endColumn = -1; } return count; } }

Comments (6)

Popular
New
Old

You must be signed in to leave a comment

Jurij Thmsn

Level 29 , Flensburg, Germany

5 May 2021, 10:13

I did it another way. I "padded" the multiarray with zeroes and looked for corners. Not the most beautiful code, but maybe interesting for some.

public static int getRectangleCount(byte[][] a) {
        int counter = 0;

        byte[][] buffed = new byte[a.length + 2][a.length+2];

        for(int i = 0; i < buffed[0].length; i++){ // buff first line
            buffed[0][i] = 0;
        }
        for(int i = 0; i < buffed[buffed.length-1].length; i++){ // buff last line
            buffed[buffed.length-1][i] = 0;
        }
        for(int i = 0; i < buffed.length; i ++){ //buff first column
            buffed[i][0] = 0;
            buffed[i][buffed[i].length -1 ] = 0; //buff last column
        }
        for(int i = 1; i < buffed.length-1; i++){ //fill "buffed" with a
            for(int j = 1; j < buffed[i].length-1; j++){
                buffed[i][j] = a[i-1][j-1];
            }
        }

        //iterate until "1" is found. If (one slot below and after)== 0 increase counter (upper left corner)
        //and (one slot over and before)== 0 : increase counter (lower right corner)
        // because either of these marks a lower-right or upper-left corner of a square
        for(int i = 1; i < buffed.length-1; i++){
            for(int j = 1; j < buffed[i].length-1; j++){
                if(buffed[i][j] == 1){
                    if(buffed[i][j+1]== 0 && buffed[i+1][j] == 0){
                        counter++;
                    }
                    if(buffed[i][j-1] == 0 && buffed[i-1][j] == 0){
                        counter++;
                    }

                }
            }
        }

        //so return count of lower-right and upper-left corners divided by 2 , because every square has two.
return counter/2;

Jurij Thmsn

Level 29 , Flensburg, Germany

5 May 2021, 10:17

the "buffed"(padded) multiarray looks now like this: (a1) 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 The "padding up" was quite messy, but I could do it without ( tried with ArrayOutOfBoundsException ). I originally wanted to look for all 4 corners of the squares but realized I just need to look for 2 of them.

Nouser

Level 36 , Germany

24 August 2020, 14:44

if it's from interst you can compare yours to my solution...

public static int getRectangleCount(byte[][] a) {
    //solution: loop through the entire array and if a 1 is found increase counter
    //and set all connected fields to 0 so they won't get counted anymore.
    int rectCount = 0;
    for (int y = 0; y < a.length; y++) {
        for (int x = 0; x < a[0].length; x++) {
            if (a[y][x] != 0) {
                rectCount++;
                resetRectangle(a, x, y);
            }
        }
    }
    return rectCount;
}

public static void resetRectangle(byte[][] a, int xStart, int yStart) {
    int yEnd = yStart, xEnd = xStart;
    //get the x2 and y2 positon of the rectangle
    for (int y = yStart; y < a.length - 1; y++) {
        if (a[y + 1][xStart] == 0)
            break;
        else
            yEnd = y + 1;
    }

    for (int x = xStart; x < a[yStart].length - 1; x++) {
        if (a[yStart][x + 1] == 0)
            break;
        else
            xEnd = x + 1;
    }

    //reset the rectangle to 0
    for (int y = yStart; y <= yEnd; y++) {
        for (int x = xStart; x <= xEnd; x++) {
            a[y][x] = 0;
        }
    }
}

Dawn( #11020889)

Level 37 , Toronto, Canada

4 January 2023, 04:18

This is the really smart and simple idea!

Thomas

Level 41 , Bayreuth, Germany

4 January 2023, 08:49

Today I'd code the 'reset method' a little bit different and use a flood fill algorithm (or smth similar) for that, like

public static int getRectangleCount(byte[][] a) {
    int rectCount = 0;
    for (int y = 0; y < a.length; y++) {
        for (int x = 0; x < a[y].length; x++) {
            if (a[y][x] != 0) {
                rectCount++;
                fill(a, x, y);
            }
        }
    }
    return rectCount;
}

public static void fill(byte[][] a, int x, int y) {
    // cell to reset is outside the array
    if (y < 0 || x < 0 || y > a.length - 1 || x > a[y].length - 1)
        return;
    // point is not in a 1 square
    if (a[y][x] == 0)
        return;

    // reset the cell and recursively invoke fill on upper, lower, left and right cell
    a[y][x] = 0;
    fill(a, x, y - 1);
    fill(a, x, y + 1);
    fill(a, x - 1, y);
    fill(a, x + 1, y);
}

Willi Ehrmann

Level 37 , Germany

17 April 2023, 01:45

I'm not even sure you need to fill with zeroes. Because the conditions on this task are very narrow. I just used one if condition to work through the 3 edge cases and the generic case. And passed the task that way.

public static int getRectangleCount(byte[][] a) {
        int count = 0;
        for ( int row = 0; row < a.length; row++ ) {
            for (int col = 0; col < a.length; col++) {
                if ((a[row][col] == 1) && (row == a.length-1 && col == a[row].length-1) ||
                        (a[row][col] == 1) && (row == a.length-1 && a[row][col+1] == 0) ||
                        (a[row][col] == 1) && (col == a[row].length-1 && a[row+1][col] == 0) ||
                        (a[row][col] == 1) && (a[row][col+1] == 0 && a[row+1][col] == 0)){
                    count++;

                }
            }
        }

        return count;
    }