^{Herausforderung Mit freundlicher Genehmigung meines University Code Challenge Contest}

---

Die Abhängigkeit von Mobiltelefonen führt dazu, dass wir sie jede Nacht bis zum maximalen Ladezustand des Akkus aufladen, sodass wir nicht das Risiko eingehen, bis Mitte des nächsten Tages keinen Strom mehr zu haben. Es gibt sogar Leute, die, wenn sie tagsüber eine kostenlose Steckdose sehen, diese für das, was passieren kann, in Rechnung stellen.

Ich bin einer von denen.

Im Laufe der Jahre habe ich meine Technik verfeinert, um den Akku nicht jede Nacht maximal aufzuladen. Mit meinen bekannten Wiederholungsroutinen ist mir klar, zu welchen Tageszeiten ich diese Teilaufladungen durchführen kann (und wie viele Einheiten der Füllstand erhöht wird) und was den Batteriestand zwischen den einzelnen Ladevorgängen senkt. Mit diesen Daten berechne ich jede Nacht den Mindestbatteriestand, mit dem ich das Haus am nächsten Tag verlassen muss, damit er nie unter meine selbst auferlegte Schwelle von zwei Einheiten fällt.

Was ich noch nicht gemeistert habe, ist dieselbe Berechnung, wenn ich die etablierte Routine verlasse und mehrere Alternativen habe, um Dinge zu tun. Es passiert zum Beispiel an den Tagen, an denen ich auf dem Weg in eine andere Stadt bin, in die ich auf unterschiedliche Weise gelangen kann.

Bei meiner ersten Herangehensweise an das Problem gehe ich davon aus, dass ich mich um ein "Schachbrett" von der oberen linken Ecke zur unteren rechten Ecke bewegen möchte. In jeder "Zelle" kann ich dem Mobiltelefon entweder einen bestimmten Betrag aufladen oder ich kann nicht und sein Ladezustand sinkt.

Herausforderung

Geben Sie bei einer FxC-Matrix von Ganzzahlen den minimalen Batteriestand aus, den ich von der oberen linken Ecke nach rechts unten benötigen muss, ohne dass der Lastpegel jemals unter 2 Einheiten fällt.

In der Matrix gibt eine positive Zahl an, wie viel ich mein Mobiltelefon aufladen kann, bevor ich meinem Pfad folgen muss, während eine negative Zahl anzeigt, dass keine Steckdosen vorhanden sind und dass der Akku des Mobiltelefons seinen Ladezustand um diesen Betrag senkt. Es wird garantiert, dass die Mengen in den Quell- und Zielzellen (obere linke und untere rechte Ecke) immer 0 sind und dass der Rest der Werte (absoluter Wert) 100 nicht überschreitet.

Beispiel
:

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

Der Weg, den ich weniger Batterie brauche, ist:

$$\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}$$

Und der minimale Akkuladestand, den ich brauche, ist 4

Anmerkungen

• Der Start wird immer die obere linke Ecke sein
• Das Ende wird immer die untere rechte Ecke sein
• Sie können nicht zu einer Zelle gehen, die Sie bereits passiert haben. Beispiel: In Position (0,1) können Sie nicht zum Anfangspunkt (0,0) gehen.
• Ihr Akkuladestand kann (aus irgendeinem Grund) nicht unter 2 fallen
• Sie können davon ausgehen, dass es immer einen Anfang und ein Ende geben wird
• Sie können die eindimensionalen Arrays bei Bedarf als mehrdimensional verwenden [1,2,3] == [[1,2,3]]
• Es kann mehrere korrekte Pfade (minimal benötigte Ladung) geben
• Ihr Ziel ist es, nur den niedrigsten benötigten Batteriestand auszugeben, nicht die Route
• Sie können nur vertikal und horizontal (nicht diagonal) gehen

Testfälle

[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 Byte

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

Probieren Sie es online aus!

Kommentiert

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 , 208 202 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

Probieren Sie es online aus!

---

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)

Probieren Sie es online aus!

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}

Probieren Sie es online aus!

C # (Visual C # Interactive Compiler) , 242 Byte

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;}

Probieren Sie es online aus!

//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;
}