seamCarving

import edu.princeton.cs.algs4.Picture;
import java.awt.*;
import java.util.*;

public class seamCarving {
	
    private int[][] colors;
    private int width;
    private int height;
    
    public seamCarving(Picture picture) {
        width=picture.width();
        height=picture.height();
        colors = new int[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                colors[i][j] = picture.get(j, i).getRGB(); //普林斯顿大学把这个函数的参数定为先写col，后写row
            }
        }
    }
    
    public Picture picture() {
        Picture picture = new Picture(width,height);
        for (int i = 0; i <height; i++)
            for (int j = 0; j <width; j++) {
                Color color = new Color(colors[i][j]);
                picture.set(j, i, color);
            }
        return picture;
    }
  
    //能量函数
    public double energy(int x, int y) {
        if (x==0||x==height-1||y==0||y==width-1) {
            return 1000.0;
        }
        else {
            int dxRed = red(colors[x - 1][y]) -red(colors[x + 1][y]);
            int dxGreen = green(colors[x - 1][y]) -green(colors[x + 1][y]);
            int dxBlue = blue(colors[x - 1][y]) -blue(colors[x + 1][y]);
            int dyRed = red(colors[x][y - 1]) - red(colors[x][y + 1]);
            int dyGreen = green(colors[x][y - 1]) - green(colors[x][y + 1]);
            int dyBlue = blue(colors[x][y - 1]) - blue(colors[x][y + 1]);
            return Math.sqrt(Math.pow(dxRed, 2) + Math.pow(dxBlue, 2) + Math.pow(dxGreen, 2) + Math.pow(dyRed, 2) + Math.pow(dyBlue, 2) + Math.pow(dyGreen, 2));
        }
    }
    
    public int[] findVerticalSeam() {
        double[][] dist=new double[height][width];
        int[][] node=new int[height][width];
        int[] seam=new int[height];
        //初始化
        for(int i=0;i<height;i++) { 
        	for(int j=0;j<width;j++) {
        		if(i==0) {
        			dist[i][j]=0.0;
        		} else {
        			dist[i][j]=Double.POSITIVE_INFINITY;
        		}
        	}
        }
        for(int i=1;i<height;i++) {
        	for(int j=0;j<width;j++) {
        		for(int k=-1;k<=1;k++) {
        			if(j+k<0||j+k>=width) continue;
        			if(dist[i][j]>(dist[i-1][j+k]+energy(i,j))) {
        				dist[i][j]=(dist[i-1][j+k]+energy(i,j));
        				node[i][j]=j+k; //记录是从哪个点过来的
        			}
        		}
        	}
        }
        int index=0;
        //找到最后一行中路径总和最短的那一个点
        for(int j=1;j<width;j++) {
        	if(dist[height-1][j]<dist[height-1][index])	{
        		index=j;
        	}
        }
        //向上回溯
        for(int i=height-1;i>=0;i--) {
        	seam[i]=index;
        	index=node[i][index];
        }
        return seam; //返回这条路径的下标数组
    }
    
    public void removeVerticalSeam(int[] seam) {
        int[][] a = new int[height][width-1];
        for (int i=0; i<height; i++) {
            System.arraycopy(colors[i],0,a[i],0,seam[i]);//参数说明：原数组，原数组起始点，目标数组，目标数组起始点，长度
            System.arraycopy(colors[i],seam[i]+1,a[i],seam[i],width-seam[i]-1);
        }
        width--;
        colors = a;
    }
    
    public void tailor(int tx,int ty) {
    	int i=0;
    	for(i=1;i<tx;i++) {
    		removeVerticalSeam(findVerticalSeam());
    	}
    	colors=transpose(colors); //矩阵转置，这样可以用同样 的函数处理高度上的缩减
    	for(i=0;i<ty;i++) {
    		removeVerticalSeam(findVerticalSeam());
    	}
    	colors=transpose(colors); //再转置回来
    	return ;
    }
    
    private int[][] transpose(int[][] origin) {
        int temp;
        temp=width;
        width=height;
        height=temp;
    	int[][] result = new int[height][width];
        for(int i = 0; i < height; i++) {
            for(int j = 0; j < width; j++) {
                result[i][j] = origin[j][i];
            }
        }
        return result;
    }
    
    private int red(int rgb) {
        return (rgb >> 16) & 0xFF;
    }
    
    private int green(int rgb) {
        return (rgb >> 8) & 0xFF;
    }
    
    private int blue(int rgb) {
        return (rgb >> 0) & 0xFF;
    }
    
	public static void main(String[] args) {
        Picture picture = new Picture("seamCarving.jpg");
        int dx=0,dy=0;
        Scanner in=new Scanner(System.in);
        dx=in.nextInt();
        dy=in.nextInt();
        in.close();
        seamCarving sc = new seamCarving(picture);
        sc.tailor(dx,dy);
        picture.show(); //显示原图像
        Picture newpicture = sc.picture();
        newpicture.show(); //把sc的colors数组包装为picture对象，再调用picture的show显示修改后的样子
        newpicture.save("swamCarving_result.jpg");
        return ;
    }
	
}