최대 이득을 가진 최단 경로 찾기

Question

Problem link 최대 무게로 최단 경로를 제공하도록 코드를 어떻게 수정할 수 있습니까?

문제 개요 : 나는 행렬을 제공하고 있는데 하나의 인덱스에서 다른 인덱스로 이동해야한다. 각 인덱스는 어떤 이득을 얻고 있기 때문에 최단 경로를 찾아야한다.)의 최대 게인 내 코드 : 코드에서

public static int min(int x , int y ,int endx,int endy,int n ,int m,int[][] p){ 
    int[] dirx ={1,-1,0,0 }; 
     int[] diry={0,0,1,-1}; 
     LinkedList<Point> som = new LinkedList<Point>(); 
     som.add(new Point(x,y)); 
     //dp[x][y]=p[x][y]; 

     while(!som.isEmpty()){ 
      Point xx = som.pop(); 
      for(int i=0;i<4;i++){ 

       int x1 = xx.x + dirx[i]; 
       int y1 = xx.y + diry[i]; 

       if(x1>=0 && x1<n && y1>=0 && y1<m && p[x1][y1]!=-1 && dp[x1][y1]==-1){ 

        dp[x1][y1] = dp[xx.x][xx.y]+ 1; 
        som.add(new Point(x1,y1)); 

       } 
      } 

     } 

    return dp[endx][endy]; 
} 

Answer 1

는

((dp[x1][y1]==-1) || ((dp[x1][y1] == dp[xx.x][xx.y] + 1) && (w[xx.x][xx.y]+p[x1][y1] > w[x1][y1]))) 

대신

(dp[x1][y1]==-1) 

추가

당신은 당신이 동일한 지점을 여러 번 추가하지 최적화 할 수 같은 길이도

의 더 나은 방법을 찾을 경우 경로 결과를 업데이트하는 것을 의미합니다,하지만 난이 생각 조건

w[x1][y1] = w[xx.x][xx.y] + p[x1][y1]; 

내부 이 특정 문제에서 필요하지 않습니다.

Answer 2

이 문제는 Dijkstra의 알고리즘을 사용하여 해결할 수 있습니다. 그러나 우리는 원래 알고리즘에서 단지 거리 대신에 거리와 이득 양을 비교할 필요가 있습니다.

다음은 나에게서 얻은 코드 힌트 중 일부입니다. 따라서 코드의 일부분 만 변경하면됩니다.

class Entry implements Comparable<Entry>{ 
    int x,y, dist, gain; 
    //Constructor is omitted. 
    public int compareTo(Entry o){ 
     if(dist != o.dist)//Compare distance first 
      return dist - o.dist; 
     return o.gain - gain;//Compare gain value 
    } 
} 

//Method signature is omitted 
PriorityQueue<Entry> q = new PriorityQueue(); 
q.add(new Entry(0,0,0,gain[0][0]); 
int[][][]dist = new int[n][m][2];//Assume size of matrix is n x m 
//Init dist array omitted 
dist[0][0][0] = 0;//Init distance 
dist[0][0][1] = gain[0][0];//Init gain amount, assume we have a gain matrix 
while(!q.isEmpty()){ 
    Entry e = q.poll(); 
    if(dist[e.x][e.y][0] == e.dist && dist[e.x][e.y][1] == e.gain){ 
     for(all valid next positions (a,b)) 
      if(dist[a][b][0] > e.dist + 1 || (dist[a][b][0] == e.dist + 1 && dist[a][b][1] < e.gain + gain[a][b]){ 
       //Notice the condition to update the dist array 
       dist[a][b][0] = e.dist + 1; 
       dist[a][b][1] = e.gain + gain[a][b]; 
       q.add(new Entry(a,b,e.dist + 1, e.gain + gain[a][b]); 
      } 
    } 
} 
return dist[n-1][m-1][1];