In computational geometry, finding patterns or specific shapes within a matrix is a common problem. A square matrix where each cell is black or white invites a variety of interesting questions, one of which is: how do we efficiently find the largest sub-square in the matrix such that all of its borders are black? This article will delineate a step-by-step algorithm to tackle this challenge and ensures an optimized solution.

Problem Definition

Given a binary $n \times n$ matrix, where each element is either 'B' (black) or 'W' (white), the task is to find the largest contiguous sub-square whose borders are entirely 'B'. Notably, the sub-square should be fully contained within the original matrix bounds.

Technical Explanation

Approach

To efficiently solve this problem, we need to ensure minimal redundancy and optimal sub-problems handling:

1. Preprocessing with Auxiliary Matrices:
   Create two auxiliary matrices horizontal and vertical , each of size $n \times n$:
   • horizontal[i][j] : Represents the number of consecutive 'B's to the left, including (i, j) .
   • vertical[i][j] : Represents the number of consecutive 'B's upwards, including (i, j) . The purpose of these matrices is to provide quick lookup for any (i, j) about how many 'B's are in a horizontal or vertical line extending from that point.
2. Dynamic Programming:
   Use dynamic programming to compute the largest square ending at every (i, j) position:
   • Move through the matrix from bottom-right corner to top-left.
   • For each (i, j), determine if it could be the lower-right corner of a potential square with a black border.
   • Utilize horizontal and vertical to verify possible square sizes.

Algorithm

Here is a step-by-step breakdown of the algorithm:

1. Initialize Auxiliary Matrices:

• After preprocessing, horizontal will look like:
  1 2 3 0 1 0 1 0 1 2 3 4 0 0 1 2
• And vertical will look like:
  1 1 1 0 2 0 2 0 3 1 3 1 0 0 4 2
• The largest black-bordered sub-square has a size of $2$, and its bottom-right corner is at position (2, 2).