Language: C++

#include<iostream>
using namespace std;
int n,m,dp[186][186][186][186],p[186][186][186][186],p2[186][186][186][186],f[186][186][186],a[186][186],tmp,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()
{
	int x1,x2,y1,y2;
	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 (int len1=1;len1<=n;++len1)
		for (int len2=1;len2<=m;++len2)
			for (int x1=1,x2;x1+len1-1<=n;++x1)
				for (int 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=1e9;
					for (int 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=1e9;
					tmp=1e9;
					for (int 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:
/tmp/ccuyYI3N.o: in function `main':
a.cc:(.text+0xbf): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccuyYI3N.o
a.cc:(.text+0xf0): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccuyYI3N.o
a.cc:(.text+0x15a): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccuyYI3N.o
a.cc:(.text+0x181): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccuyYI3N.o
a.cc:(.text+0x1b8): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccuyYI3N.o
a.cc:(.text+0x1f2): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccuyYI3N.o
a.cc:(.text+0x21d): relocation truncated to fit: R_X86_64_PC32 against symbol `a' defined in .bss section in /tmp/ccuyYI3N.o
a.cc:(.text+0x255): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccuyYI3N.o
a.cc:(.text+0x28e): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccuyYI3N.o
a.cc:(.text+0x40c): relocation truncated to fit: R_X86_64_PC32 against symbol `f' defined in .bss section in /tmp/ccuyYI3N.o
a.cc:(.text+0x4a1): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status