Autor da análise: 
Atol
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2798
Resumo
É dada uma matriz n por m, que deve ser "dividida" em "pedaços" de forma a maximizar a quantidade desses "pedaços", onde n e m estão entre 1 e 20.
Pedaço:
A matriz é constituída de caracteres "A" a "Z" , "a" a "Z" , "0" a "9". Um pedaço contém todas as ocorrências dos caracteres
contidos no pedaço, ou seja, dois pedaços distintos não podem conter um mesmo caractere.
Divisão (Corte):
Porém, temos uma regra para efetuar as divisões em um pedaço (que inicialmente é uma matriz). Uma divisão só pode ser feita com cortes horizontais e verticais iniciados nas bordas de um pedaço.
É mais fácil visualizar isso em um desenho que está no enunciado do problema.
Uma outra informação importante é que os caracteres na matriz inicial sempre formam pedaços "conexos", ou seja, caracteres iguais estão sempre em um bloco conexo, vizinhos horizontal ou verticalmente.
====
Genéricamente, temos 6 tipos de cortes a serem realizados, para cada linha e coluna escolhidas.
Vamos considerar a matriz a seguir (indexada de 1 a 3).
| 1 | 2 | 3 |
| 4 | 6 | 7 |
| 8 | 9 | 10 |
Considerando um corte que passa pela linha 2, coluna 1, temos:
| 1 | | | 2 | 3 |
| 4 | | | 6 | 7 |
| - | | | - | - |
| 8 | | | 9 | 10 |
Agora veja que dado esse corte, podemos separar o pedaço inicial de 6 maneiras:
(Consideram apenas a linha horizontal ou vertical)
1.Cima - Baixo
2.Esquerda - Direita
(Consideram ambas as linhas)
(CSD = Canto superior direito, CSE = Canto superior esquerdo, CID = Canto inferior direito, DIE = Canto inferior direito)
3.CSD + CSE + CID - CIE
4.CSD + CSE + CIE - CID
5.CID + CIE + CSD - CSE
6.CID + CIE + CSE - CSD, exemplo para este caso :
| 1 | | | ||
| 4 | | | ||
| - | | | - | - |
| 8 | | | 9 | 10 |
| | | 2 | 3 | |
| | | 6 | 7 | |
| - | | | - | - |
| | |
Para cada um dos cortes, basta verificar se ambos "pedaços" gerados são realmente pedaços, ou seja, respeitam a propriedade dada no enunciado. Se algum corte respeitar a propriedade, basta realizá-lo, e tentar efetuar cortes nos pedaços gerados.
Dica 1: Na verdade só é necessário verificar se um dos lados cortados é um pedaço, pois isso implica que o outro também é, se não for um pedaço vazio (que não contém nenhum caractere).
Dica 2: Tal verificação pode ser realizada percorrendo apenas as bordas do corte, olhando para os caracteres na fronteira do corte.
Assim, para cada corte que vamos tentar realizar, fazemos O(n+m) operações.
Para um dado pedaço, precisamos tentar fazer O(n*m) cortes.
O número de pedaços formados é no máximo 26+26+10 ( Maiúsculas + Minúsculas + Dígitos ).
Portanto, o algoritmo custa O ( (n*m)*(n+m) * (62) ).
Algo em torno do O( n^4 ), porém, tive que fazer bastante limpeza de código para conseguir passar esse problema.
Discuta o problema