¿Algún día estaremos en Tailandia?

Descripción

Uno de los paises que más te gusta es Tailandia y sus templos hermosos que hay, quisieras ir de paseo y presenciar las hermosas vistas que este país ofrece, lamentablemente no tienes dinero y necesitas empezar a trabajar de programador para empezar a guardar y así un día visitar todo el mundo. En tu estudio para preparte para los problemas que te pudieran poner en las entrevistas de las empresas, te encontraste con uno que llamó bastante tu atención.

Se te da una matriz de \(N\) filas por \(M\) columnas, en donde cada casilla contiene un 1 o un 0. Tu tarea es encontrar una ruta válida tal que, al escribir los valores de cada casilla que hay en la ruta, formes el valor binario más grande posible y lo conviertas a su base decimal. Una ruta válida es aquella en donde puedes empezar y terminar en cualquier casilla de la matriz, de tal forma que visites todas y cada una de las casillas que tiene la matriz, pero solo puedes pasar una vez por cada casilla. Si estás en una casilla, solo puedes irte a sus casillas adyacentes (arriba, abajo, izquierda y derecha).

Problema

Dado la matriz binaria de \(N\) x \(M\), encuentra la mejor ruta válida tal que el valor expresado en decimal de esa ruta sea el máximo.

Entrada

• En la primera línea habrá dos números: \(N\) y \(M\), el tamaño de la matriz.
• En las siguientes \(N\) líneas habrá \(M\) números, correspondientes a la matriz en la fila \(N_i\) y columna \(M_i\).

Salida

Un número que representa el máximo valor convertido a decimal de la mejor ruta válida posible.

Ejemplos

Entrada

2 2
1 0
1 1

Salida

14

Explicación: A continuación se enlistan todas las posibles rutas válidas:

• \((1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,1).\) Esta ruta daría el siguiente valor binario: \(1011\). En decimal es \(11\).
• \((1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (1,2).\) Esta ruta daría el siguiente valor binario: \(1110\). En decimal es \(14\).
• \((1,2) \rightarrow (1,1) \rightarrow (2,1) \rightarrow (2,2).\) Esta ruta daría el siguiente valor binario: \(0111\). En decimal es \(7\).
• \((1,2) \rightarrow (2,2) \rightarrow (2,1) \rightarrow (1,1).\) Esta ruta daría el siguiente valor binario: \(0111\). En decimal es \(7\).
• \((2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (2,2).\) Esta ruta daría el siguiente valor binario: \(1101\). En decimal es \(13\).
• \((2,1) \rightarrow (2,2) \rightarrow (1,2) \rightarrow (1,1).\) Esta ruta daría el siguiente valor binario: \(1101\). En decimal es \(13\).
• \((2,2) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2).\) Esta ruta daría el siguiente valor binario: \(1110\). En decimal es \(14\).
• \((2,2) \rightarrow (1,2) \rightarrow (1,1) \rightarrow (2,1).\) Esta ruta daría el siguiente valor binario: \(1011\). En decimal es \(11\).

Por lo tanto, la ruta válida con valor máximo es la segunda o penúltima (\(14\)).

Entrada

3 3
1 0 0
1 1 0
0 1 0

Salida

450

Explicación: Una de las posibles rutas válidas con valor máximo es:

• \((2,2) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (3,3) \rightarrow (3,2) \rightarrow (3,1)\).

Esta ruta daría el siguiente valor binario: \(111000010\). En decimal es \(450\). Está demostrado que no hay una ruta con un mejor valor.

Límites

• \(1 \leq N, M \leq 5\).
• La matriz solo contiene \(1\)'s o \(0\)'s.