Submission #8560968

---

Source Code Expand

#include <cstdio>
#include <algorithm>

const int MN = 188;

int N, M, J;
char a[MN][MN];
int f[MN][MN][MN], g[MN][MN][MN];

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i) scanf("%s", a[i] + 1);
	int tN = N - 1, tM = M - 1;
	while (tN) ++J, tN >>= 1;
	while (tM) ++J, tM >>= 1;
	for (int l = 1; l <= N; ++l)
		for (int r = l; r <= N; ++r) {
			f[l][r][M + 1] = M;
			for (int j = M; j >= 1; --j) {
				int o = l == r || (a[l][j] == a[r][j] && f[l][r - 1][j] >= j);
				if (!o) f[l][r][j] = j - 1;
				else f[l][r][j] = a[l][j] == a[l][j + 1] ? f[l][r][j + 1] : j;
			}
		}
	for (int l = 1; l <= M; ++l)
		for (int r = l; r <= M; ++r) {
			g[l][r][N + 1] = N;
			for (int i = N; i >= 1; --i) {
				int o = l == r || (a[i][l] == a[i][r] && g[l][r - 1][i] >= i);
				if (!o) g[l][r][i] = i - 1;
				else g[l][r][i] = a[i][l] == a[i + 1][l] ? g[l][r][i + 1] : i;
			}
		}
	if (f[1][N][1] == M) return puts("0"), 0;
	for (int k = 1; k <= J; ++k) {
		for (int l = 1; l <= N; ++l)
			for (int r = l; r <= N; ++r)
				for (int j = 1; j <= M; ++j)
					f[l][r][j] = f[l][r][f[l][r][j] + 1];
		for (int l = 1; l <= M; ++l)
			for (int r = l; r <= M; ++r)
				for (int i = 1; i <= N; ++i)
					g[l][r][i] = g[l][r][g[l][r][i] + 1];
		for (int i = 1; i <= N; ++i)
			for (int j = 1; j <= M; ++j) {
				static int A[MN], B[MN];
				for (int z = i; z <= N; ++z) A[z] = f[i][z][j];
				for (int z = j; z <= M; ++z) B[z] = g[j][z][i];
				A[N + 1] = j - 1, B[M + 1] = i - 1;
				for (int z = i; z <= N; ++z)
					for (int w = A[z]; w > A[z + 1]; --w)
						g[j][w][i] = std::max(g[j][w][i], z);
				for (int z = j; z <= M; ++z)
					for (int w = B[z]; w > B[z + 1]; --w)
						f[i][w][j] = std::max(f[i][w][j], z);
			}
		if (f[1][N][1] == M) return printf("%d\n", k), 0;
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:11:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
./Main.cpp:12:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= N; ++i) scanf("%s", a[i] + 1);
                                                    ^

Judge Result