Largest Plus Sign

You are given an integer n, which defines an n x n binary grid. Initially, all values in the grid are 1s. You are also given an array mines, where each element mines[i] = [row, col] indicates that the cell grid[row][col] should be a 0.

Your task is to find the order of the largest axis-aligned plus sign of 1s contained in the final grid. If no plus sign of 1s exists (i.e., the grid contains no 1s), you should return 0.

An axis-aligned plus sign of order k is defined by:

  A center cell grid[r][c] which must be 1.
  Four "arms" of 1s extending up, down, left, and right from the center.
  The length of each arm must be at least k-1.

This means the order k is determined by the shortest arm extending from the center. For a plus sign centered at (r, c), the order is 1 + min(up, down, left, right), where up is the number of consecutive 1s above the center, down is the number below, and so on.

Input Format:

The first line contains a single integer n, the size of the grid.

The second line contains an integer m, the number of mines.

The next m lines each contain two space-separated integers, r and c, representing the coordinates of a mine.

Output Format:

Your function should return a single integer representing the order of the largest plus sign.

Note:

A brute-force approach that checks every cell as a potential center and expands outwards would be O(n^3), which is too slow. A more efficient O(n^2) dynamic programming approach is required.