1139.cpp (922B)
1 class Solution { 2 public: 3 int largest1BorderedSquare(vector<vector<int>> &grid) { 4 static int top[101][101], left[101][101]; 5 const int n = size(grid), m = size(grid[0]); 6 7 for (int i = 1; i <= n; i++) { 8 for (int j = 1; j <= m; j++) { 9 left[i][j] = grid[i - 1][j - 1] ? left[i][j - 1] + 1 : 0; 10 top[i][j] = grid[i - 1][j - 1] ? top[i - 1][j] + 1 : 0; 11 } 12 } 13 14 for (int s = min(m, n); s > 0; s--) { 15 for (int i = 0; i <= n - s; i++) { 16 for (int j = 0; j <= m - s; j++) { 17 if (top[i + s][j + 1] < s) continue; 18 if (top[i + s][j + s] < s) continue; 19 if (left[i + 1][j + s] < s) continue; 20 if (left[i + s][j + s] < s) continue; 21 return s * s; 22 } 23 } 24 } 25 26 return 0; 27 } 28 };