普林斯顿算法课part2第二周作业_seamcarving

   private void DijkstraSP(boolean isVertical, double[][] energy, double[] distTo, int[] edgeTo) {
       int V = width * height;  
       for (int v = 0; v < V; v++) {
           distTo[v] = Double.POSITIVE_INFINITY;
           edgeTo[v] = 0;
       }
       int initLen = width;
       if (!isVertical) initLen = height;
       IndexMinPQ<Double> pq = new IndexMinPQ<Double>(V);       
       for (int v = 0; v < initLen; v++) {
           distTo[v] = MAX_ENERGY;
           pq.insert(v, distTo[v]);
       }
       boolean notFinStat = true;
       while (!pq.isEmpty() && notFinStat) { 
           relax(pq.delMin(), isVertical, energy, distTo, edgeTo, pq);           
           for (int i = V - 1; i > V - initLen; i--) 
               if (distTo[i] != Double.POSITIVE_INFINITY) {
                   notFinStat = false;
                   break;
               }
       }
   }   
   private void relax(int v, boolean isVertical, double[][] energy, double[] distTo, int[] edgeTo, IndexMinPQ<Double> pq) {
       int x, y, w;
       double weight;
       int seamWidth = width, seamHeight = height;  
       if (!isVertical) {
           seamWidth = height; 
           seamHeight = width;
       }
       x = v % seamWidth; 
       y = v / seamWidth;
       if (x == 0 || x == seamWidth -1 || y == seamHeight - 1) 
           return;    
       for (int delta = -1; delta < 2; delta++) {     
           w = (y+1) * seamWidth + (x + delta);
           weight = energy[x + delta][y + 1];      
           if (distTo[w] > distTo[v] + weight) {
               distTo[w] = distTo[v] + weight;
               edgeTo[w] = v;
               if(y + 1 == seamHeight - 1) return;
               if (pq.contains(w)) pq.changeKey(w, distTo[w]);
               else pq.insert(w, distTo[w]);
           }
       }    
   }

   private int[] findSeam(boolean isVertical, double[] distTo, int[] edgeTo) {
       int minIndex = 0;       
       double minDist = Double.POSITIVE_INFINITY;
       int seamWidth = width, seamHeight = height;
       if (!isVertical) {     
           seamWidth = height;
           seamHeight = width;
       }
       int[] seamPath = new int [seamHeight];
       for (int i = 0; i < seamWidth; i++)      
           if (distTo[(seamHeight - 1) * seamWidth + i] < minDist) {
           minIndex = (seamHeight - 1) * seamWidth + i;
           minDist = distTo[(seamHeight -1) * seamWidth + i];
       }    
       for (int i = seamHeight - 1; i > 0 ; i--) {
           seamPath[i] = minIndex % seamWidth;
           minIndex = edgeTo[minIndex];
       }
       if (seamPath.length > 1) seamPath[0] = seamPath[1];
       return seamPath;
   }   

   private double[][] energyTranspose(int W, int H, boolean isTranspose) {
       double[][] result = new double[W][H];
       for (int y = 0; y < H; y++)
           for (int x = 0; x < W; x++) {
           if (isTranspose) result[x][y] = energy(y, x);
           else result[x][y] = energy(x, y);
       }   
       return result;        
   }   

   public void removeVerticalSeam(int[] seam) {
       if (seam.length != height || width <= 1) 
           throw new java.lang.IllegalArgumentException();
       checkSeam(seam, width);
       int[][] copy = new int[width-1][height];
       for (int y = 0; y < height; y++) {
           for (int x = 0; x < width; x++) {
               if (x < seam[y]) copy[x][y] = colorRGB[x][y];
               else if (x > seam[y]) copy[x-1][y] = colorRGB[x][y];
           }
       }
       width--;
       colorRGB = copy;  
       picture();
   }