Different Squares

Description:

Given a rectangular matrix containing only digits, calculate the number of different 2 × 2 squares in it.

Example

For

matrix = [[1, 2, 1],
          [2, 2, 2],
          [2, 2, 2],
          [1, 2, 3],
          [2, 2, 1]]

the output should be
differentSquares(matrix) = 6.

Here are all 6 different 2 × 2 squares:

  • 1 2
    2 2
  • 2 1
    2 2
  • 2 2
    2 2
  • 2 2
    1 2
  • 2 2
    2 3
  • 2 3
    2 1

Input/Output

  • [time limit] 3000ms (cs)
  • [input] array.array.integer matrix

    Constraints:
    1 ≤ matrix.length ≤ 100,
    1 ≤ matrix[i].length ≤ 100,
    0 ≤ matrix[i][j] ≤ 9.

  • [output] integer

    The number of different 2 × 2 squares in matrix.

Tests:
Solution(C#):

int differentSquares(int[][] matrix) {
    int lenM = matrix.Length;
    List<Rectangle> rects = new List<Rectangle>();
    if(lenM>=1 && lenM<=100) {
        for(int i=0;i<lenM-1;i++) {
            int lenI = matrix[i].Length;
            for(int j=0;j<lenI-1;j++) {
                Rectangle rect = GetRectangle(matrix, i, j);
                if(!rects.Contains(rect)) {
                    rects.Add(rect);
                }
            }
        }
        return rects.Count;
    }
    else
        throw new ArgumentOutOfRangeException();
}
Rectangle GetRectangle(int[][] matrix, int i, int j) {
    return new Rectangle(matrix[i][j],matrix[i][j+1],matrix[i+1][j],matrix[i+1][j+1]);
}
class Rectangle : IEquatable<Rectangle> {
    public Rectangle(int x11, int x21, int x12, int x22) {
        this.X11 = x11;
        this.X12 = x12;
        this.X21 = x21;
        this.X22 = x22;
    }
    public int X11 { get; set; }
    public int X12 { get; set; }
    public int X21 { get; set; }
    public int X22 { get; set; }

    public bool Equals(Rectangle other) {
        if (this.X11 == other.X11 && this.X12 == other.X12
            && this.X21 == other.X21 && this.X22 == other.X22) {
            return true;
        }
        else {
            return false;
        }
    }
}

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s