矩阵中求最大递增路径-查看文章

矩阵中求最大递增路径

发表于:2019-03-27 17:08:23 分类:JAVA 阅读:889次

image

123456.png

代码如下:

public class IncrementalPathTest {
    private int[][] nums;
    private int maxStep;
    private List<String> bestRoad = new ArrayList<>();

    public IncrementalPathTest(int[][] nums){
        this.nums = nums;
    }

    public static void main(String[] args) {
        int mx =3;
        int my =5;
        int[][] nums = new int[mx][my];
        int[] x0 = {1,2,3,8,6};
        int[] x1 = {0,2,4,5,3};
        int[] x2 = {2,2,6,7,9};
        nums[0] = x0;
        nums[1] = x1;
        nums[2] = x2;
        IncrementalPathTest test = new IncrementalPathTest(nums);
        test.printNums();
        test.run();
        List<String> bestRoad = test.getBestRoad();
        System.out.println(test.getMaxStep());
        System.out.println("最大递增路径为:"+bestRoad);
    }
    public void run(){
        for (int x=0;x<nums.length;x++){
            for(int y=0;y<nums[0].length;y++){
                canMove(x, y,nums[x][y]+"");
            }
        }
    }

    public void printNums(){
        for (int x=0;x<nums.length;x++){
            for(int y=0;y<nums[0].length;y++){
                System.out.printf(nums[x][y]+" ");
            }
            System.out.println();
        }
    }

    public void canMove(int x,int y,String s){
        boolean canLeft = canLeft(x, y);
        boolean canRight = canRight(x, y);
        boolean canUp = canUp(x, y);
        boolean canDown = canDown(x, y);
        int mx=x,my=y;
        if(!canLeft&&!canRight&&!canUp&&!canDown){
            isMax(s);
        }
        if(canLeft){
            my = my - 1;
            canMove(mx,my,s+nums[mx][my]);
        }
        mx=x;my=y;
        if(canRight){
            my = my + 1;
            canMove(mx,my,s+nums[mx][my]);
        }
        mx=x;my=y;
        if(canUp){
            mx = mx - 1;
            canMove(mx,my,s+nums[mx][my]);
        }
        mx=x;my=y;
        if(canDown){
            mx = mx + 1;
            canMove(mx,my,s+nums[mx][my]);
        }
    }
    private void isMax(String s){
        if(s.length()>maxStep){
            maxStep = s.length();
            bestRoad = new ArrayList<>(maxStep);
            for (char c:s.toCharArray()) {
                bestRoad.add(c+"");
            }
        }
    }
    private boolean canLeft(int x,int y){
        if(y>0&&nums[x][y]<nums[x][y-1]){
            return true;
        }
        return false;
    }
    private boolean canRight(int x,int y){
        if(y<nums[0].length-1&&nums[x][y]<nums[x][y+1]){
            return true;
        }
        return false;
    }
    private boolean canUp(int x,int y){
        if(x>0&&nums[x][y]<nums[x-1][y]){
            return true;
        }
        return false;
    }
    private boolean canDown(int x,int y){
        if(x<nums.length-1&&nums[x][y]<nums[x+1][y]){
            return true;
        }
        return false;
    }

    public int getMaxStep() {
        return maxStep;
    }

    public List<String> getBestRoad() {
        return bestRoad;
    }
}


关键词:算法,矩阵,路径


验证码: