[C/C++] BOJ #1051 - Number Square

The problem itself is quite simple. Its difficulty is rated as Silver III, so it’s not particularly hard. However, the correct answer rate is relatively low, around 37%.

---

You are given an N×M matrix of numbers, and the task is to select four numbers that form a square — meaning the four numbers should be aligned parallel to the rows and columns, forming the corners of a square — and all four numbers must be the same. The smallest such square would be 1×1.

finding rectangles

---

I solved the problem using a brute-force approach. I first selected the smaller value between N and M, and then decreased the size step by step, checking whether there exist four numbers that satisfy the condition. Once such numbers are found, the result is printed immediately.

Here’s the source code I wrote. Please use it as a reference only.

//----------------------------------------------------------
//    baekjoon #1051 - Number Square
//        - by Aubrey Choi
//        - created at 2019-07-01
//----------------------------------------------------------
#include <stdio.h>

bool search(char map[][51], int n, int m, int sq)
{
    for(int i = 0; i < n-sq; i++) for(int j = 0; j < m-sq; j++)
    {
        char s = map[i][j];
        if(s==map[i][j+sq] && s==map[i+sq][j] && s==map[i+sq][j+sq]) return true;
    }
    return false;
}

int main()
{
    char map[50][51];
    int n, m, sq;
    scanf("%d%d", &n, &m);
    sq = n<m?n:m;
    for(int i = 0; i < n; i++) scanf("%s", map[i]);
    while(sq-- && !search(map, n, m, sq));
    printf("%d\n", (sq+1)*(sq+1));
}