Максимальный квадрат с 0 внутри - PullRequest
Новая
       13

Максимальный квадрат с 0 внутри

0 голосов
/ 12 сентября 2018

Вопрос о максимальном квадрате в https://leetcode.com/problems/maximal-square/description/ легко решить с помощью DP.Но как решить следующий вопрос:

Похоже на вопрос о максимальном квадрате, но допускает 0 внутри квадрата, «внутри» означает, что граница квадрата должна быть 1 .Например, с учетом следующей матрицы:

1 0 1 0 0

1 0 1 1 1

1 1 1 0 1

1 0 11 1

Возврат 9.

Обновление: поскольку матрица 3 * 3 в правом нижнем углу соответствует требованию, граница должна быть все 1, а внутри может быть 0квадрат.

Я придумал алгоритм O (n ^ 3): возьмите maze[i][j] в качестве правого нижнего угла квадрата, если maze[i][j] == 1, перечислите длину ребра квадрата.Если длина ребра равна 3, подумайте, образуют ли maze[i - 2][j - 2], maze[i][j - 2], maze[i - 2][j], maze[i][j] квадрат с числами в каждом ребре, равными 1.

Есть ли лучший алгоритм?

1 Ответ

0 голосов
/ 17 сентября 2018

Ваша проблема может быть решена в O (n * m) сложности времени и пространства, где n - общее количество строк, а m - общее количество столбцов в матрице. , Вы можете посмотреть код ниже, где я прокомментировал, чтобы сделать его понятным. Пожалуйста, дайте мне знать, если у вас есть какие-либо сомнения. 

#include <bits/stdc++.h>
using namespace std;

void precalRowSum(vector< vector<int> >& grid, vector< vector<int> >&rowSum, int n, int m) {
// contiguous sum upto jth position in ith row
 for (int i = 0; i < n; ++i) {
     int sum = 0;
     for (int j = 0; j < m; ++j) {
          if (grid[i][j] == 1) {
              sum++;
          } else {
              sum = 0;
          }
          rowSum[i][j] = sum;
      }
   }
 }

 void precalColSum(vector< vector<int> >& grid, vector< vector<int> >&colSum, int n, int m) {
// contiguous sum upto ith position in jth column
for (int j = 0; j < m; ++j) {
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        if (grid[i][j] == 1) {
            sum++;
        } else {
            sum = 0;
        }
        colSum[i][j] = sum;
     }
   }
 }

int solve(vector< vector<int> >& grid, int n, int m) {  
  vector< vector<int> >rowSum(n, vector<int>(m, 0));
  vector< vector<int> >colSum(n, vector<int>(m, 0));
  // calculate rowwise sum for 1
  precalRowSum(grid, rowSum, n, m);
  // calculate colwise sum for 1
  precalColSum(grid, colSum, n, m);
  vector< vector<int> >zerosHeight(n, vector<int>(m, 0));
  int ans = 0;
  for (int i = 0; i < (n - 1); ++i) {
    for (int j = 0; j < m; ++j) {
        zerosHeight[i][j] = ( grid[i][j] == 0 );
        if (grid[i][j] == 0 && i > 0) {
            zerosHeight[i][j] += zerosHeight[i - 1][j];
        }
    }
    if (i == 0) continue;
    // perform calculation on ith row
    for (int j = 1; j < m; ) {
        int height = zerosHeight[i][j];
        if (!height) {
            j++;
            continue;
        }
        int cnt = 0;
        while (j < m && height ==  zerosHeight[i][j]) {
            j++;
            cnt++;
        }
        if ( j == m) break;
        if (cnt == height && (i - cnt) >= 0 ) {
            // zeros are valid, now check validity for boundries
            // Check validity of upper boundray, lower boundary, left boundary, right boundary respectively
            if (rowSum[i - cnt][j] >= (cnt + 2) && rowSum[i + 1][j] >= (cnt + 2) &&
                colSum[i + 1][j - cnt - 1] >= (cnt + 2) && colSum[i + 1][j] >= (cnt + 2) ){
                ans = max(ans, (cnt + 2) * (cnt + 2) );
            }
        }
    }
  }
  return ans;
}
int main() {
 int n, m;
 cin>>n>>m;
 vector< vector<int> >grid;
 for (int i = 0; i < n; ++i) {
    vector<int>tmp;
    for (int j = 0; j < m; ++j) {
        int x;
        cin>>x;
        tmp.push_back(x);
    }
    grid.push_back(tmp);
 }
 cout<<endl;

 cout<< solve(grid, n, m) <<endl;
 return 0;
}
...