Language: C++

struct Info{
	short table[10][10],num;
};

short W,H,ans,POW[11];
short first_table[10][10],max_size[10][10];

bool rangeCheck(short row,short col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}

inline void copyTable(Info& to,short from[10][10],short base_row){

	for(short row = base_row; row < H; row++){
		for(short col = 0; col < W; col++)to.table[row][col] = from[row][col];
	}
}


void recursive(Info info,short base_row,short base_col,short pre_must_add){

	if(info.num == ans)return;

	if(base_row == H){ //??¨???????????????????????§?????£?????´???
		//ans = min(ans,info.num);
		ans = info.num;
		return;
	}

	if(info.table[base_row][base_col] == -1){ //????????????????¶???????????????§????????´???

		//???????????????????????????????§?
		if(base_col == W-1){
			recursive(info,base_row+1,0,pre_must_add);
		}else{
			recursive(info,base_row,base_col+1,pre_must_add);
		}
		return;
	}

	//?°?????????¨???1???????????°??????????????????????????????????????????[[????????§??????????????????????????????????????]]
	short new_num = 0;
	for(short i = 0; i < max_size[base_row][base_col]; i++){
		for(short k = 0; k < max_size[base_row][base_col]; k++){
			if(info.table[base_row+i][base_col+k] == 0){
				new_num++;
				break;
			}
		}
		if(new_num != 0)break;
	}

	if(new_num == 0){ //??°?????????????????????????????????

		if(base_col == W-1){
			recursive(info,base_row+1,0,pre_must_add);
		}else{
			recursive(info,base_row,base_col+1,pre_must_add);
		}
	}else{

		//????????????(?????????????????¢???????????????????????´?????????):???dfs??§??°????°????????????????????????±???????????????
		if(info.table[base_row][base_col] != 0){

			if(base_col == W-1){
				recursive(info,base_row+1,0,pre_must_add);
			}else{
				recursive(info,base_row,base_col+1,pre_must_add);
			}
		}

		//????????????????????????
		for(short i = 0; i < max_size[base_row][base_col]; i++){
			for(short k = 0; k < max_size[base_row][base_col]; k++){
				info.table[base_row+i][base_col+k]++;
			}
		}

		short must_add = 0;
		bool FLG = false;
		//?°?????????¨??????????????§??????????????????????????°????¨????
		for(short row = base_row; row < H; row++){
			for(short col = 0; col < W; col++){
				if(info.table[row][col] == 0 && first_table[row][col] == 1){
					must_add++;
				}else if(info.table[row][col] == 0 && first_table[row][col] > 1){
					FLG = true;
				}
			}
		}

		if(FLG)must_add++;

		info.num++;

		if(info.num+must_add < ans){
			if(base_col == W-1){
				recursive(info,base_row+1,0,must_add);
			}else{
				recursive(info,base_row,base_col+1,must_add);
			}
		}
	}
}


void func(){

	for(short row = 0; row < H; row++){
		for(short col = 0; col < W; col++){
			scanf("%d",&first_table[row][col]);
			first_table[row][col] -= 1;
		}
	}

	bool FLG;
	short size;
	//?????????????????????????????§????????????????±???????
	for(short row = 0; row < H; row++){
		for(short col = 0; col < W; col++){
			if(first_table[row][col] == -1){
				max_size[row][col] = 0;
			}else{
				size = 1;

				FLG = true;

				while(true){
					for(short i = 0; i < size; i++){
						for(short k = 0; k < size; k++){
							if(rangeCheck(row+i,col+k) == false || first_table[row+i][col+k] == -1){
								FLG = false;
								break;
							}
						}
						if(!FLG)break;
					}
					if(!FLG){
						size -= 1;
						break;
					}
					size++;
				}

				max_size[row][col] = size;

				//1??????????????????????????????????????????????????????????????????????????§?????????????????§??????????????´?????????????????????????????????
				for(short calc_size = 1; calc_size <= size; calc_size++){
					for(short i = 0; i < calc_size; i++){
						for(short k = 0; k < size; k++){
							first_table[row+i][col+k]++;
						}
					}
				}
			}
		}
	}

	Info start;
	start.num = 0;
	short pre_must_add = 0;
	FLG = false;

	for(short row = 0; row < H; row++){
		for(short col = 0; col < W; col++){
			if(first_table[row][col] == -1){
				start.table[row][col] = -1;
			}else{
				if(first_table[row][col] == 1){
					pre_must_add++;
				}else{
					FLG = true;
				}
				start.table[row][col] = 0;
			}
		}
	}

	if(FLG)pre_must_add++;

	ans = BIG_NUM;

	recursive(start,0,0,pre_must_add);

	prshortf("%d\n",ans);
}

short main(){

	for(short i = 0; i < 11; i++)POW[i] = pow(2,i);

	while(true){
		scanf("%d %d",&W,&H);
		if(W == 0 && H == 0)break;

		func();
	}

	return 0;
}

Compiler output:
a.cc: In function 'void func()':
a.cc:114:25: error: 'scanf' was not declared in this scope
  114 |                         scanf("%d",&first_table[row][col]);
      |                         ^~~~~
a.cc:184:15: error: 'BIG_NUM' was not declared in this scope
  184 |         ans = BIG_NUM;
      |               ^~~~~~~
a.cc:188:9: error: 'prshortf' was not declared in this scope; did you mean 'short'?
  188 |         prshortf("%d\n",ans);
      |         ^~~~~~~~
      |         short
At global scope:
cc1plus: error: '::main' must return 'int'
a.cc: In function 'int main()':
a.cc:193:47: error: 'pow' was not declared in this scope
  193 |         for(short i = 0; i < 11; i++)POW[i] = pow(2,i);
      |                                               ^~~
a.cc:196:17: error: 'scanf' was not declared in this scope
  196 |                 scanf("%d %d",&W,&H);
      |                 ^~~~~