Language: C++

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <random>
#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

int h, w;
int t[SIZE][SIZE], t2[SIZE][SIZE];
int max_size[11][11] = {};
int covered[11][11] = {};
set<pair<pair<ll,ll>,int> > visited;

int ans;

void dfs(int y, int x, int counter = 0, ll hash = 0, ll hash2 = 0){
  //debug(ans);
  int diff[11][11] = {};
  if(ans <= counter) return;
  if(visited.find({{hash,hash2},y*w+x}) != visited.end()) return;
  
  if(y == h){
    ans = min(ans, counter);
    return;
  }

  if(max_size[y][x] == 0 || covered[y][x])
     dfs(y + (x == w-1), (x + 1)%w, counter, hash);
  
  if(max_size[y][x] != 0){
    ll newhash = hash, newhash2 = hash2;
    int diffcounter = 0;
    for(int i=0;i<max_size[y][x];i++)
      for(int j=0;j<max_size[y][x];j++)
        if(covered[y+i][x+j] == 0){
          diff[y+i][x+j] = covered[y+i][x+j] = 1;
          newhash ^= t[y+i][x+j];
          newhash2 ^= t2[y+i][x+j];
          diffcounter++;
        }

    if(diffcounter)
      dfs(y + (x == w-1), (x + 1)%w, counter+1, newhash);

    for(int i=0;i<max_size[y][x];i++)
      for(int j=0;j<max_size[y][x];j++)
        if(diff[y+i][x+j] == 1){
          covered[y+i][x+j] = 0;
        }
  }
  
  visited.insert({{hash,hash2},y*w+x});
}

bool solve(){
  int sp[11][11] = {};
  int p[11][11];
  debug(clock());
  
  scanf("%d%d", &w, &h);

  if(h == 0) return false;


  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      scanf("%d", p[i]+j);
      sp[i][j] = p[i][j];
    }
  }

  for(int i=h;i>0;i--)
    for(int j=0;j<=w;j++)
      sp[i-1][j] += sp[i][j];

  for(int i=0;i<=h;i++)
    for(int j=w;j>0;j--)
      sp[i][j-1] += sp[i][j];


  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      int p = min(h-i, w-j);
      max_size[i][j] = 0;
      for(int k=1;k<=p;k++){
        if(sp[i][j] + sp[i+k][j+k] - sp[i+k][j] - sp[i][j+k] == k*k) max_size[i][j] = k;
        //debug(sp[i][j] + sp[i+k][j+k] - sp[i+k][j] - sp[i][j+k]);
      }
      //debug(max_size[i][j]);
    }
  }

  debug(clock());

  visited = set<pair<pair<ll,ll>,int> >();
  ans = INF;
  dfs(0,0);
  printf("%d\n", ans);

  return true;
}

int main(){
  std::random_device rd;
  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      t[i][j] = ((ll)rd() << 32) + rd(); 
      t2[i][j] = ((ll)rd() << 32) + rd(); 
    }
  }

  debug(clock());
  
  while(solve());
  
  return 0;
}



Compiler output:
/tmp/ccSphcN5.o: in function `dfs(int, int, int, long long, long long)':
a.cc:(.text+0x4d): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/ccSphcN5.o
a.cc:(.text+0x62): relocation truncated to fit: R_X86_64_PC32 against symbol `visited' defined in .bss section in /tmp/ccSphcN5.o
a.cc:(.text+0xd3): relocation truncated to fit: R_X86_64_PC32 against symbol `visited' defined in .bss section in /tmp/ccSphcN5.o
a.cc:(.text+0x122): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/ccSphcN5.o
a.cc:(.text+0x132): relocation truncated to fit: R_X86_64_PC32 against symbol `ans' defined in .bss section in /tmp/ccSphcN5.o
a.cc:(.text+0x16b): relocation truncated to fit: R_X86_64_PC32 against symbol `max_size' defined in .bss section in /tmp/ccSphcN5.o
a.cc:(.text+0x1a6): relocation truncated to fit: R_X86_64_PC32 against symbol `covered' defined in .bss section in /tmp/ccSphcN5.o
a.cc:(.text+0x230): relocation truncated to fit: R_X86_64_PC32 against symbol `max_size' defined in .bss section in /tmp/ccSphcN5.o
a.cc:(.text+0x2af): relocation truncated to fit: R_X86_64_PC32 against symbol `covered' defined in .bss section in /tmp/ccSphcN5.o
a.cc:(.text+0x2fa): relocation truncated to fit: R_X86_64_PC32 against symbol `covered' defined in .bss section in /tmp/ccSphcN5.o
a.cc:(.text+0x342): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status