^{Reto tomado con permiso de mi concurso de desafío de código universitario}

---

La dependencia que tenemos de los teléfonos móviles nos hace cargarlos todas las noches hasta el nivel máximo de la batería, por lo que no corremos el riesgo de quedarnos sin energía a mediados del día siguiente. Incluso hay personas que, cuando ven un enchufe gratuito durante el día, lo cobran por lo que pueda suceder.

Yo soy uno de ellos.

Con los años, he perfeccionado mi técnica para no cargar la batería al máximo todas las noches. Con mis rutinas repetitivas perfectamente conocidas, tengo claro en qué momentos del día podré hacer esas recargas parciales (y cuántas unidades aumentará el nivel) y qué reduce el nivel de batería entre cada carga. Con estos datos, cada noche calculo el nivel mínimo de batería con el que tengo que salir de la casa al día siguiente para que nunca caiga por debajo de mi umbral autoimpuesto de dos unidades.

Lo que aún no he logrado dominar es ese mismo cálculo cuando dejo la rutina establecida y tengo varias alternativas para hacer las cosas. Ocurre, por ejemplo, en los días en que me dirijo a otra ciudad a la que puedo llegar de diferentes maneras.

En mi primer acercamiento al problema, supongo que quiero moverme alrededor de un "tablero de ajedrez", desde la esquina superior izquierda a la esquina inferior derecha. En cada "celda" puedo cargar el móvil una cantidad específica, o no puedo y su nivel de carga baja.

Desafío

Dada una matriz de enteros FxC, produzca la cantidad mínima de nivel de batería que necesito para ir desde la esquina superior izquierda a la esquina inferior derecha sin que el nivel de carga caiga por debajo de 2 unidades.

En la matriz, un número positivo indica cuánto puedo cargar mi teléfono móvil antes de tener que continuar siguiendo mi camino, mientras que un número negativo indica que no hay salidas y que la batería del móvil baja su nivel de carga en esa cantidad. Se garantiza que las cantidades en las celdas de origen y destino (esquina superior izquierda e inferior derecha) son siempre 0 y que el resto de los valores (valor absoluto) no exceden de 100.

Ejemplo
dado:

$$\begin{bmatrix} 📱&-1&1&-1 \\ -1&-1&-1&-1 \\ -1&1&-1&-1 \\ 1&1&-1&0 \end{bmatrix}$$

El camino que necesito menos batería es:

$$\begin{bmatrix} 📱&-1&1&-1 \\ \color{blue}{-1}&-1&-1&-1 \\ \color{blue}{-1}&1&-1&-1 \\ \color{blue}{1}&\color{blue}{1}&\color{blue}{-1}&0 \end{bmatrix}$$

Y la cantidad mínima de batería que necesito es 4

Notas

• El inicio siempre será la esquina superior izquierda
• El final siempre será la esquina inferior derecha
• No puedes ir a una celda que ya has pasado. Ejemplo: una vez en la posición (0,1), no puede ir al punto inicial (0,0)
• Su nivel de batería no puede (por ningún motivo) ser inferior a 2
• Puedes asumir que siempre habrá un principio y un final
• Puede tomar las matrices unidimensionales como multidimensionales si necesita [1,2,3] == [[1,2,3]]
• Puede haber múltiples rutas correctas (carga mínima necesaria)
• Su objetivo es producir solo el nivel de batería inicial más bajo necesario, no la ruta
• Solo puedes ir vertical y horizontalmente (no diagonalmente)

Casos de prueba

[0, 0] => 2
[0, 1, 0] => 2
[0, -1, 0] => 3
[0, 15, -20, 5, 0] => 7
[[0, -3],[-5, 0]] => 5
[[0, -5, -9, 5], [-3, 5, 2, -2], [2, -4, -4, 0]] => 5
[[0, -1, 1, -1], [-1, -1, -1, -1], [-1, 1, -1, -1], [1, 1, -1, 0]] => 4

JavaScript (ES7),  162 156  154 bytes

m=>(M=g=(x,y,n,k)=>m.map((r,Y)=>[r[x+1]]+[m[y+1]]?r.map((v,X)=>r[1/v&&(x-X)**2+(y-Y)**2==1&&g(X,Y,u=v+n,k<u?k:u,r[X]=g),X]=v):M=M>k?M:k))(0,0,0)|M<0?2-M:2

Pruébalo en línea!

Comentado

m => (                          // m[] = input matrix
  M =                           // initialize M to a non-numeric value
  g = (x, y, n, k) =>           // g = recursive depth-first search function
    m.map((r, Y) =>             // for each row r[] at position Y in m[]:
      [r[x + 1]] +              //   if either r[x + 1]
      [m[y + 1]] ?              //   or m[y + 1] is defined:
        r.map((v, X) =>         //     for each value v at position X in r[]:
          r[                    //
            1 / v &&            //       if v is numeric
            (x - X) ** 2 +      //       and the squared Euclidean distance
            (y - Y) ** 2 == 1   //       between (x, y) and (X, Y) is 1:
            &&                  //
              g(                //         do a recursive call:
                X, Y,           //           with (X, Y)
                u = v + n,      //           with n = n + v
                k < u ? k : u,  //           with k = min(k, n + v)
                r[X] = g        //           set r[X] to a non-numeric value
              ),                //         end of recursive call
            X                   //       then restore r[X]
          ] = v                 //       to its initial value
        )                       //     end of inner map()
      :                         //   else (we've reached the bottom right corner):
        M = M > k ? M : k       //     update M to max(M, k)
    )                           // end of outer map()
)(0, 0, 0) |                    // initial call to g with x = y = n = 0 and k undefined
M < 0 ? 2 - M : 2               // return 2 - M if M is negative, or 2 otherwise

Python 2 , 208202 bytes

lambda s:2-f(s)
def f(s,x=0,y=0):
 if x>-1<y<s[y:]>[]<s[y][x:]!="">s[y][x]:k=s[y][x];s[y][x]="";return k+min(0,max([len(s[y+1:]+s[y][x+1:])and f(eval(`s`),x+a/3-1,y+a%3-1)for a in 7,1,5,3]))
 return-9e9

Pruébalo en línea!

---

Python 2 , 217 211 bytes

i=input()
X,Y=len(i[0]),len(i)
s=[[0]*4+[i]];r=[]
for m,l,x,y,g in s:
 if X>x>-1<y<Y<"">g[y][x]:r+=[m]*(Y-y<2>X-x);l+=g[y][x];g[y][x]="";s+=[[min(m,l),l,x+a/3-1,y+a%3-1,eval(`g`)]for a in 7,1,5,3]
print 2-max(r)

Pruébalo en línea!

R , 224 220 217 213 210 bytes

f=function(x,m=rbind(0,cbind(0,x,0),0),i=2,j=2,p=F,k=c(1:-1,0,0,-1:1),b=Inf,`^`=min){m[i,j]=0
for(h in 1:4)b=b^'if'(all(c(R<-i+k[h],C<-j+k[h+4])>dim(x)),max(2,2-cumsum(p)^0),if(v<-m[R,C])b^f(x,m,R,C,c(p,v)))
b}

Pruébalo en línea!

C # (compilador interactivo de Visual C #) , 242 bytes

a=>{int m=1<<31,n=~m;void g(int w,int x,int y,int z){for(int i=4,t,c,d,e;i-->0;)try{t=a[c=i<1?w-1:i<2?w+1:w,d=i>2?x-1:i>1?x+1:x];n=t==0&z<n?z:n;a[c,d]=m;e=y+t<2?2-y-t:0;if(t!=m)g(c,d,y+t+e,z+e);a[c,d]=t;}catch{}}a[0,0]=m;g(0,0,2,2);return n;}

Pruébalo en línea!

//a: input matrix
a=>{
  // m: marker for used cells
  // n: result, initialized to a huge value
  int m=1<<31,n=~m;
  // recursive function
  // w: 1st dim coordinate
  // x: 2nd dim coordinate
  // y: current charge level
  // z: initial charge for current path
  void g(int w,int x,int y,int z){
    // i: loop variable
    // t: temp holds overwritten value
    // c: adjacent 1st dim coordinate
    // d: adjacent 2nd dim coordinate
    // e: delta charge needed
    for(int i=4,t,c,d,e;i-->0;)
      // avoid index out of range errors
      // by using try/catch
      try{
        // determine neighbor
        // coordinates and save value
        t=a[c=i<1?w-1:i<2?w+1:w,
            d=i>2?x-1:i>1?x+1:x];
        // if we have found a 0, check if
        // initial charge is lower than the
        // lowest so far. save it if it is.
        n=t==0&z<n?z:n;
        // mark current cell used
        a[c,d]=m;
        // determine if we need to
        // increase the initial charge
        e=y+t<2?2-y-t:0;
        // make recursive call if current
        // cell was not previously in use
        if(t!=m)g(c,d,y+t+e,z+e);
        // restore current cell value
        a[c,d]=t;
      }catch{}
  }
  // mark starting cell used
  a[0,0]=m;
  // start the recursive function
  g(0,0,2,2);
  // return the result to the caller
  return n;
}