Расчет резьбы шва в двумерном массиве

Question

    for (int h = 0; h < 4; h++) {

        int minValue = a[h][0];
        for (int i = h; i < h + 1; i++) {
            for (j = w; j < w + 3; j++) {
                if (a[i][j] < minValue) {
                    minValue = a[i][j];

                }

            }
        }
        System.out.println("Minimum Value = " + minValue);

    }

Я хочу найти вырезку шва, но алгоритм не работает хорошо. Как я знаю, нужно найти минимальное значение по выбранному индексу

Answer 1

Я не уверен, что ваш код найдет минимальный шов: для этого существует «простой» подход к динамическому программированию:

      private static int[][] findHorizontalSeam(double[][] energyTable) {
        int[][] seam;
        int width = energyTable.length;
        int height = energyTable[0].length;
        // seamDynamic is the table we will use for dynamic programming.
        double[][] seamDynamic = new double[width][height];
        int[][] backtracker = new int[width][height];
        double minimum;
        // horizontal seam.
        seam = new int[energyTable.length][2];

        // Loops over the energy table and finds the lowest energy path.
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                if (x == 0) {
                    seamDynamic[x][y] = energyTable[x][y];
                    backtracker[x][y] = -1;
                } else {
                    // every other column.
                    // need to special case the top/bottom.
                    if (y == 0) {
                        minimum = Math.min(seamDynamic[x - 1][y], seamDynamic[x - 1][y + 1]);
                        if (minimum == seamDynamic[x - 1][y]) {
                            // add backtracker.
                            backtracker[x][y] = 1;
                        } else { // y + 1
                            // add backtracker.
                            backtracker[x][y] = 2;
                        }
                    } else if (y == (height - 1)) {
                        minimum = Math.min(seamDynamic[x - 1][y], seamDynamic[x - 1][y - 1]);
                        if (minimum == seamDynamic[x - 1][y]) {
                            // add backtracker.
                            backtracker[x][y] = 1;
                        } else { // y - 1
                            // add backtracker.
                            backtracker[x][y] = 0;
                        }
                    } else {
                        minimum = Math.min(seamDynamic[x - 1][y - 1], Math.min(seamDynamic[x - 1][y], seamDynamic[x - 1][y + 1]));
                        if (minimum == seamDynamic[x - 1][y - 1]) {
                            // add backtracker.
                            backtracker[x][y] = 0;
                        } else if (minimum == seamDynamic[x - 1][y]) {
                            // add backtracker.
                            backtracker[x][y] = 1;
                        } else { // y + 1
                            // add backtracker.
                            backtracker[x][y] = 2;
                        }
                    }
                    seamDynamic[x][y] = energyTable[x][y] + minimum;
                }
            }
        }

        // now that we have computed the paths, we need to backtrace the minimum one.
        // 0 --> y - 1.
        // 1 --> y.
        // 2 --> y + 1.
        // first we need to find the min at the end.
        double min_num = seamDynamic[width - 1][0];
        int min_index = 0;
        for (int y = 0; y < height; y++) {
            if (min_num > seamDynamic[width - 1][y]) {
                min_index = y;
                min_num = seamDynamic[width - 1][y];
            }
        }

        // now that we have the min we need to backtrace it.
        int y_index = min_index;
        int x_index = width - 1;
        seam[x_index][0] = x_index;
        seam[x_index][1] = y_index;
        int backtrack;
        while (x_index > 0) {
            backtrack = backtracker[x_index][y_index];
            if (backtrack != -1) {
                if (backtrack == 0) {
                    y_index = y_index - 1;
                } else if (backtrack == 1) {
                    y_index = y_index;
                } else { // = 2
                    y_index = y_index + 1;
                }
            } else {
                y_index = y_index;
            }
            x_index = x_index - 1;

            seam[x_index][0] = x_index;
            seam[x_index][1] = y_index;
        }
    }

Вы можете найти полный код для вырезателя швов на Java здесь .