Consider computing the answer with DP (Dynamic Programming), in which the problem is (recursively) divided into subrectangles.

For each subrectangle of size \(A \times B\), he can destroy the blocks within it with stamina point \(C=\max(A,B)\), because we can always choose a rectangle of size \(C \times C\) that entirely covers the subrectangle. Is it possible to destroy this subrectangle consuming less than stamina power \(C\)?

In fact, the following property holds.

If all the blocks within a subrectangle of size \(A \times B\) can be destroyed with less than stamina power \(C\), then there exists an empty row or column, and it is possible to destroy all the blocks so that any operations are done for the rectangles that do not overlap the empty row or column.

By this property, if there exists an empty row or column within the subrectangle, we may divide it by the row and column and recursively solve the smaller problems.

Therefore, this problem can be solved in a total of \(O(N^5)\) or \(O(N^6)\) time. At a glance, it may result in TLE (Time Limit Exceeded), but the constant factor is small enough, so if you use fast language, \(O(N^6)\) is still enough for the time limit. Please also refer to the sample code for implementation detail.

#include<bits/stdc++.h>

using namespace std;

int dp[51][51][51][51];
vector<string> s;

int rep(int lx,int ly,int rx,int ry){
  if(lx>rx){return 0;}
  if(ly>ry){return 0;}
  if(dp[lx][ly][rx][ry]<1000){return dp[lx][ly][rx][ry];}
  dp[lx][ly][rx][ry]=max(ry-ly+1,rx-lx+1);
  for(int i=lx;i<=rx;i++){
    bool ok=true;
    for(int j=ly;j<=ry;j++){
      if(s[i][j]=='#'){ok=false;break;}
    }
    if(ok){
      dp[lx][ly][rx][ry]=min(dp[lx][ly][rx][ry],rep(lx,ly,i-1,ry)+rep(i+1,ly,rx,ry));
    }
  }
  for(int i=ly;i<=ry;i++){
    bool ok=true;
    for(int j=lx;j<=rx;j++){
      if(s[j][i]=='#'){ok=false;break;}
    }
    if(ok){
      dp[lx][ly][rx][ry]=min(dp[lx][ly][rx][ry],rep(lx,ly,rx,i-1)+rep(lx,i+1,rx,ry));
    }
  }
  return dp[lx][ly][rx][ry];
}

int main(){
  int n;
  cin >> n;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      for(int k=0;k<n;k++){
        for(int l=0;l<n;l++){dp[i][j][k][l]=100000;}
      }
    }
  }
  s.resize(n);
  for(int i=0;i<n;i++){cin >> s[i];}
  cout << rep(0,0,n-1,n-1) << '\n';
  return 0;
}

If the test case is generated randomly, the answer will be almost \(N\). For example, if each square is set to to # at the probability of \(\frac{1}{2}\), the answer will be \(N\) for most cases.
One way is to include cases of spares grid. This way, we can obtain many test cases with answer far from \(N\).
Another way is to do the operations in the reverse order. Specifically, we can do as follows.

1. Choose a rectangular region.
2. Place blocks to the rectangular region with appropriate density. We may fill all the squares within the selected region with blocks, or place very few of them.
3. Repeat 1. and 2. several times.

By varying the parameters like the number and size of rectangular regions and the density, we can generate strong test cases for some extent.