^{Wyzwanie Podjęte za zgodą mojego konkursu na University Code Challenge}

---

Zależność od telefonów komórkowych sprawia, że ​​co noc ładujemy je do maksymalnego poziomu baterii, więc nie ryzykujemy wyczerpania energii do połowy następnego dnia. Są nawet ludzie, którzy widząc bezpłatny punkt w ciągu dnia, naliczają go za to, co może się zdarzyć.

Jestem jednym z nich.

Przez lata doskonaliłem swoją technikę, aby nie ładować baterii do maksimum każdej nocy. Dzięki moim doskonale znanym powtarzalnym procedurom mam jasność, o jakich porach dnia będę w stanie wykonać te częściowe doładowania (i o ile jednostek poziom się zwiększy) i co obniża poziom baterii między poszczególnymi ładowaniami. Na podstawie tych danych co noc obliczam minimalny poziom naładowania baterii, z którym muszę wyjść z domu następnego dnia, aby nigdy nie spadł poniżej mojego narzuconego progu dwóch jednostek.

To, czego jeszcze nie udało mi się opanować, to takie same obliczenia, kiedy odchodzę od ustalonej rutyny i mam kilka alternatywnych rzeczy do zrobienia. Zdarza się to na przykład w dniach, gdy jestem w drodze do innego miasta, do którego mogę dotrzeć na różne sposoby.

W moim pierwszym podejściu do problemu zakładam, że chcę poruszać się po „szachownicy”, od lewego górnego rogu do prawego dolnego rogu. W każdej „komórce” mogę albo naładować komórkę określoną kwotą, albo nie mogę i jej poziom obciążenia spada.

Wyzwanie

Biorąc pod uwagę macierz FxC liczb całkowitych, wypisz minimalną ilość poziomu baterii, którą muszę przejść od lewego górnego rogu do prawego dolnego rogu, bez obciążenia nigdy poniżej 2 jednostek.

W matrycy liczba dodatnia wskazuje, ile mogę naładować mój telefon komórkowy, zanim muszę wznowić podążanie moją ścieżką, a liczba ujemna oznacza, że ​​nie ma gniazdek i że bateria telefonu komórkowego obniża poziom naładowania o tę kwotę. Gwarantuje się, że ilości w komórkach źródłowej i docelowej (lewy górny i prawy dolny róg) zawsze wynoszą 0, a reszta wartości (wartość bezwzględna) nie przekracza 100.

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

Ścieżka, której potrzebuję mniej baterii to:

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

A potrzebna mi minimalna ilość baterii to 4

Notatki

• Start zawsze będzie lewym górnym rogiem
• Koniec zawsze będzie prawym dolnym rogiem
• Nie możesz przejść do komórki, którą już przekazałeś. Przykład: w pozycji (0,1) nie można przejść do punktu początkowego (0,0)
• Poziom naładowania baterii nie może (z jakiegokolwiek powodu) przekroczyć 2
• Możesz założyć, że zawsze będzie początek i koniec
• W razie potrzeby można traktować tablice jednowymiarowe jako wielowymiarowe [1,2,3] == [[1,2,3]]
• Może istnieć wiele prawidłowych (minimalnych potrzebnych opłat) ścieżek
• Twoim celem jest uzyskanie najniższego wymaganego początkowego poziomu naładowania akumulatora, a nie trasy
• Możesz poruszać się tylko w pionie i poziomie (nie po przekątnej)

Przypadki testowe

[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 bajtów

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

Wypróbuj online!

Skomentował

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 bajtów

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

Wypróbuj online!

---

Python 2 , 217 211 bajtów

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)

Wypróbuj online!

R , 224 220 217 213 210 bajtów

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}

Wypróbuj online!

C # (interaktywny kompilator Visual C #) , 242 bajty

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

Wypróbuj online!

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