Language: C++

#include<iostream>
#define N 186
using namespace std;
short n,m,dp[N][N][N][N],p[N][N][N][N],p2[N][N][N][N],tmp;
int f[186][186][186],a[186][186],P;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9')
		c=getchar();
	while ('0'<=c&&c<='9')
	{
		sum=sum*10+c-'0';
		c=getchar();
	}
	return sum;
}
int main()
{
	char s;
	n=read(),m=read();
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=m;++j)
		{
			s=getchar();
			if (s=='.')
				a[i][j]=1;
			if (s=='#')
				a[i][j]=2;
		}
		getchar();
	}
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
		{
			f[i][j][j]=a[i][j];
			for (int k=j+1;k<=m;++k)
			{
				if (a[i][k]==f[i][j][k-1])
					f[i][j][k]=a[i][k];
				else
					f[i][j][k]=0;
			}
		}
	for (int i=1;i<=n;++i)
		for (int j=i;j<=n;++j)
			for (int k=1;k<=m;++k)
				for (int l=k;l<=m;++l)
					dp[i][j][k][l]=1e9;
	for (short len1=1;len1<=n;++len1)
		for (short len2=1;len2<=m;++len2)
			for (short x1=1,x2;x1+len1-1<=n;++x1)
				for (short y1=1,y2;y1+len2-1<=m;++y1)
				{
					x2=x1+len1-1;
					y2=y1+len2-1;
					if (len1==1&&f[x2][y1][y2])
					{
						dp[x1][x2][y1][y2]=0;
						continue;
					}
					if (len1!=1&&f[x2][y1][y2]!=0&&dp[x1][x2-1][y1][y2]==0&&f[x2][y1][y2]==f[x2-1][y1][y2])
					{
						dp[x1][x2][y1][y2]=0;
						continue;
					}
					P=p[x1+1][x2][y1][y2];
					if (P==0)
						P=1e5;
					for (short s=max(p[x1][x2-1][y1][y2],x1);s<=min(P,x2-1);++s)
						if (max(dp[x1][s][y1][y2],dp[s+1][x2][y1][y2])+1<dp[x1][x2][y1][y2])
						{
							p[x1][x2][y1][y2]=s;
							dp[x1][x2][y1][y2]=max(dp[x1][s][y1][y2],dp[s+1][x2][y1][y2])+1;
						}
					P=p2[x1][x2][y1+1][y2];
					if (P==0)
						P=1e5;
					tmp=1e9;
					for (short s=max(p[x1][x2][y1][y2-1],y1);s<=min(P,y2-1);++s)
						if (max(dp[x1][x2][y1][s],dp[x1][x2][s+1][y2])+1<tmp)
						{
							p2[x1][x2][y1][y2]=s;
							tmp=max(dp[x1][x2][y1][s],dp[x1][x2][s+1][y2])+1;
						}
					dp[x1][x2][y1][y2]=min(dp[x1][x2][y1][y2],tmp);
				}
	printf("%d\n",dp[1][n][1][m]);
	return 0;
}

Compiler output:
a.cc: In function 'int main()':
a.cc:51:56: warning: overflow in conversion from 'double' to 'short int' changes value from '1.0e+9' to '32767' [-Woverflow]
   51 |                                         dp[i][j][k][l]=1e9;
      |                                                        ^~~
a.cc:81:45: warning: overflow in conversion from 'double' to 'short int' changes value from '1.0e+9' to '32767' [-Woverflow]
   81 |                                         tmp=1e9;
      |                                             ^~~
/tmp/ccTIPmmc.o: in function `main':
a.cc:(.text+0xc2): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccTIPmmc.o
a.cc:(.text+0xf3): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccTIPmmc.o
a.cc:(.text+0x161): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccTIPmmc.o
a.cc:(.text+0x188): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccTIPmmc.o
a.cc:(.text+0x1bf): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccTIPmmc.o
a.cc:(.text+0x1f9): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccTIPmmc.o
a.cc:(.text+0x224): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccTIPmmc.o
a.cc:(.text+0x25c): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccTIPmmc.o
a.cc:(.text+0x295): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccTIPmmc.o
a.cc:(.text+0x429): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccTIPmmc.o
a.cc:(.text+0x4ca): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status