#include <bits/stdc++.h>
using namespace std;
int res, hcn[35][35], f[35][35][35][35] , m, n;
int hcn2 (int x1, int y1, int x2, int y2)
{
if ( f[x1][y1][x2][y2] != -1) return ( f[x1][y1][x2][y2]);
int tong=0;
for ( int i=x1; i<=x2; i++ )
for ( int j=y1; j<=y2; j++) tong += hcn[i][j];
res=m*n;
if ( tong == 0 || tong == (x2-x1+1)*(y2-y1+1))
{
f[x1][y1][x2][y2] = 1;
return ( f[x1][y1][x2][y2] );
}
for (int i=x1; i<x2; i++) if (res > (hcn2(x1,y1,i,y2) + hcn2 (i+1,y1,x2,y2))) res= f[x1][y1][i][y2]+f[i+1][y1][x2][y2];
for (int i=y1; i<y2; i++) if (res>(hcn2(x1,y1,x2,i) + hcn2 (x1,i+1,x2,y2)) ) res=f[x1][y1][x2][i]+f[x1][i+1][x2][y2];
f[x1][y1][x2][y2] =res;;
return res;
}
int main()
{
cin>>m>>n;
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++) cin>>hcn[i][j];
memset(f, -1, sizeof(f));
// cout<<f[0][0][0][0]<<endl;
cout << hcn2(1,1,m,n);
//for (int i=1; i<=m; i++)
//for (int j=1; j<=n; j++) cout <<f[i][j][i][j]<<endl;
return 0;
}
Mọi người cho e hỏi code của e chạy test chỉ ra 7 mà kq của test là 8
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?