27
Апр
2021

Необходимо снизить потребление памяти

Распространение волны и поиск кратчайшего пути на торе. Превышается обозначеный порог по потреблению памяти, необходимо оптимизировать, сильно не перекраивая код. Поля - препятствия = 1 Поля - свободные = 0

public static void main(String[] args) {

    boolean flag = false;
    boolean flag2 = false;
    short i = 0;
    short ii = 0;
    short gt = 0;
    short gt2 = 0;

    String[] pars;


    short count = 0;

    short n = 0;
    short m = 0;

    ArrayList<String> points = new ArrayList<>();
    ArrayList<String> points2 = new ArrayList<>();

    short[][] field = new short[0][];

    short Sn = 0;
    short Sm = 0;
    short Fn = 0;
    short Fm = 0;

    boolean top = true;
    boolean bottom = true;
    boolean left = true;
    boolean right = true;

    short nRows = 0;
    short mColumns = 0;

    try (BufferedReader bf = new BufferedReader(new InputStreamReader(System.in))){
        //ввод строки с размером тора
        pars = bf.readLine().split(" ");

        nRows = Short.parseShort(pars[0]);
        mColumns = Short.parseShort(pars[1]);

        field = new short[nRows][mColumns];

        //ввод строки с координатами финиша и старта на торе
        pars = bf.readLine().split(" ");
        Sn = Short.parseShort(pars[0]);
        Sm = Short.parseShort(pars[1]);
        Fn = Short.parseShort(pars[2]);
        Fm = Short.parseShort(pars[3]);

        //заполнение тора
        for(short g = 0; g < nRows; g++){
            pars = bf.readLine().split(" ");
            for(short x = 0; x < mColumns; x++){
                if(Short.parseShort(pars[x]) == 1){
                    field[g][x] = -2;
                }else {
                    field[g][x] = Short.parseShort(pars[x]);
                }
            }
        }
    }catch(IOException e){
        e.printStackTrace();
    }

    field[Sn][Sm] = -1;

    //распространение волны
    for (;;) {

        count++;
        if (count == 1) {

            if(Sm != field[0].length-1) {
                if (field[Sn][Sm + 1] == 0) {
                    field[Sn][Sm + 1] = count;
                    points.add(Sn + " " + (Sm + 1));
                }
            }else{
                if (field[Sn][field[0].length - mColumns] == 0) {
                    field[Sn][field[0].length - mColumns] = count;
                    points.add(Sn + " " + (field[0].length - mColumns));
                }
            }

            if(Sm != field[0].length-mColumns) {
                if (field[Sn][Sm - 1] == 0) {
                    field[Sn][Sm - 1] = count;
                    points.add(Sn + " " + (Sm - 1));
                }
            }else{
                if (field[Sn][field[0].length - 1] == 0) {
                    field[Sn][field[0].length - 1] = count;
                    points.add(Sn + " " + (field[0].length - 1));
                }
            }

            if(Sn != field.length-1) {
                if (field[Sn + 1][Sm] == 0) {
                    field[Sn + 1][Sm] = count;
                    points.add((Sn + 1) + " " + Sm);
                }
            }else{
                if (field[field.length-nRows][Sm] == 0) {
                    field[field.length-nRows][Sm] = count;
                    points.add((field.length-nRows) + " " + Sm);
                }
            }

            if(Sn != field.length-nRows) {
                if (field[Sn - 1][Sm] == 0) {
                    field[Sn - 1][Sm] = count;
                    points.add((Sn - 1) + " " + Sm);
                }
            }else{
                if (field[field.length-1][Sm] == 0) {
                    field[field.length-1][Sm] = count;
                    points.add((field.length-1) + " " + Sm);
                }
            }

        }else{

            if(count >= 2) {
                count--;
            }

            for (;;) {
                if (!points.isEmpty()){

                    if (gt == 0) {
                        gt++;
                        count++;
                    }

                    pars = points.get(i).split(" ");
                    n = Short.parseShort(pars[0]);
                    m = Short.parseShort(pars[1]);
                    points.remove(i);

                    if(m != field[0].length-1) {
                        if (field[n][m + 1] == 0) {
                            field[n][m + 1] = count;
                            if(n == Fn && m + 1 == Fm){
                                flag = true;
                                break;
                            }
                            points2.add(n + " " + (m + 1));
                        }
                    }else{
                        if (field[n][field[0].length-mColumns] == 0) {
                            field[n][field[0].length-mColumns] = count;
                            if(n == Fn && (field[0].length-mColumns == Fm)){
                                flag = true;
                                break;
                            }
                            points2.add(n + " " + (field[0].length-mColumns));
                        }
                    }

                    if(m != field[0].length-mColumns) {
                        if (field[n][m - 1] == 0) {
                            field[n][m - 1] = count;
                            if(n == Fn && (m - 1 == Fm)){
                                flag = true;
                                break;
                            }
                            points2.add(n + " " + (m - 1));
                        }
                    }else{
                        if (field[n][field[0].length-1] == 0) {
                            field[n][field[0].length-1] = count;
                            if(n == Fn && (field[0].length-1 == Fm)){
                                flag = true;
                                break;
                            }
                            points2.add(n + " " + (field[0].length-1));
                        }
                    }

                    if(n != field.length-1) {
                        if (field[n + 1][m] == 0) {
                            field[n + 1][m] = count;
                            if(n+1 == Fn && m == Fm){
                                flag = true;
                                break;
                            }
                            points2.add((n + 1) + " " + m);
                        }
                    }else{
                        if (field[field.length-nRows][m] == 0) {
                            field[field.length-nRows][m] = count;
                            if(field.length-nRows == Fn && m == Fm){
                                flag = true;
                                break;
                            }
                            points2.add((field.length-nRows) + " " + m);
                        }
                    }

                    if(n != field.length-nRows) {
                        if (field[n - 1][m] == 0) {
                            field[n - 1][m] = count;
                            if(n-1 == Fn && m == Fm){
                                flag = true;
                                break;
                            }
                            points2.add((n - 1) + " " + m);
                        }
                    }else{
                        if (field[field.length - 1][m] == 0) {
                            field[field.length - 1][m] = count;
                            if(field.length - 1 == Fn && m == Fm){
                                flag = true;
                                break;
                            }
                            points2.add((field.length - 1) + " " + m);
                        }
                    }

                }else{
                    gt = 0;
                    break;
                }
            }

            if(flag){
                break;
            }

            for (;;) {
                if (!points2.isEmpty()) {

                    if (gt2 == 0) {
                        gt2++;
                        count++;
                    }

                    pars = points2.get(ii).split(" ");
                    n = Short.parseShort(pars[0]);
                    m = Short.parseShort(pars[1]);
                    points2.remove(ii);

                    if(m != field[0].length-1) {
                        if (field[n][m + 1] == 0) {
                            field[n][m + 1] = count;
                            if(n == Fn && m + 1 == Fm){
                                flag = true;
                                break;
                            }
                            points.add(n + " " + (m + 1));
                        }
                    }else{
                        if (field[n][field[0].length-mColumns] == 0) {
                            field[n][field[0].length-mColumns] = count;
                            if(n == Fn && (field[0].length-mColumns == Fm)){
                                flag = true;
                                break;
                            }
                            points.add(n + " " + (field[0].length-mColumns));
                        }
                    }

                    if(m != field[0].length-mColumns) {
                        if (field[n][m - 1] == 0) {
                            field[n][m - 1] = count;
                            if(n == Fn && m - 1 == Fm){
                                flag = true;
                                break;
                            }
                            points.add(n + " " + (m - 1));
                        }
                    }else{
                        if (field[n][field[0].length-1] == 0) {
                            field[n][field[0].length-1] = count;
                            if(n == Fn && (field[0].length-1 == Fm)){
                                flag = true;
                                break;
                            }
                            points.add(n + " " + (field[0].length-1));
                        }
                    }

                    if(n != field.length-1) {
                        if (field[n + 1][m] == 0) {
                            field[n + 1][m] = count;
                            if(n+1 == Fn && m == Fm){
                                flag = true;
                                break;
                            }
                            points.add((n + 1) + " " + m);
                        }
                    }else{
                        if (field[field.length-nRows][m] == 0) {
                            field[field.length-nRows][m] = count;
                            if(field.length-nRows == Fn && m == Fm){
                                flag = true;
                                break;
                            }
                            points.add((field.length-nRows) + " " + m);
                        }
                    }

                    if(n != field.length-nRows) {
                        if (field[n - 1][m] == 0) {
                            field[n - 1][m] = count;
                            if(n-1 == Fn && m == Fm){
                                flag = true;
                                break;
                            }
                            points.add((n - 1) + " " + m);
                        }
                    }else{
                        if (field[field.length - 1][m] == 0) {
                            field[field.length - 1][m] = count;
                            if(field.length - 1 == Fn && m == Fm){
                                flag = true;
                                break;
                            }
                            points.add((field.length - 1) + " " + m);
                        }
                    }

                }else{
                    gt2 = 0;
                    break;
                }
            }

            if(flag){
                break;
            }

            if(points.isEmpty() & points2.isEmpty()){
                break;
            }

        }
    }

    points.clear();
    points2.clear();
    
    //восстановление кратчайшего пути
    for(;;){

        if(Fm != field[0].length-1) {
            if ((field[Fn][Fm + 1] == (field[Fn][Fm] - 1)) && (field[Fn][Fm + 1] != 0)) {
                points.add("W");
                Fm++;
                continue;
            }else{
                if (field[Fn][Fm + 1] == -1) {
                    points.add("W");
                    flag2 = true;
                    break;
                }else {

                    right = false;
                }
            }
        }else{
            if ((field[Fn][field[0].length - mColumns] == (field[Fn][field[0].length-1] - 1)) & (field[Fn][field[0].length - mColumns] != 0)) {
                points.add("W");
                Fm = (short) (field[0].length - mColumns);
                continue;
            }else{
                if (field[Fn][field[0].length - mColumns] == -1) {
                    points.add("W");
                    flag2 = true;
                    break;
                }else {
                    right = false;
                }
            }
        }

        if(Fm != field[0].length-mColumns) {
            if ((field[Fn][Fm - 1] == (field[Fn][Fm] - 1)) && (field[Fn][Fm - 1] != 0)) {
                points.add("E");
                Fm--;
                continue;
            }else{
                if (field[Fn][Fm - 1] == -1) {
                    points.add("E");
                    flag2 = true;
                    break;
                }else {
                    left = false;
                }
            }
        }else{
            if (((field[Fn][field[0].length - 1] == ((field[Fn][field[0].length - mColumns] - 1)))) & (field[Fn][field[0].length - 1] != 0)) {
                points.add("E");
                Fm = (short) (field[0].length - 1);
                continue;
            }else{
                if (field[Fn][field[0].length - 1] == -1) {
                    points.add("E");
                    flag2 = true;
                    break;
                }else {
                    left = false;
                }
            }
        }

        if(Fn != field.length-1) {
            if ((field[Fn + 1][Fm] == (field[Fn][Fm] - 1)) && (field[Fn + 1][Fm] != 0)) {
                points.add("N");
                Fn++;
                continue;
            }else{
                if (field[Fn + 1][Fm] == -1) {
                    points.add("N");
                    flag2 = true;
                    break;
                }else {
                    bottom = false;
                }
            }
        }else{
            if ((field[field.length-nRows][Fm] == (field[field.length-1][Fm] - 1)) & (field[field.length - nRows][Fm] != 0)) {
                points.add("N");
                Fn = (short) (field.length-nRows);
                continue;
            }else{
                if (field[field.length-nRows][Fm] == -1) {
                    points.add("N");
                    flag2 = true;
                    break;
                }else {
                    bottom = false;
                }
            }
        }

        if(Fn != field.length-nRows) {
            if ((field[Fn - 1][Fm] == (field[Fn][Fm] - 1)) && (field[Fn - 1][Fm] != 0)) {
                points.add("S");
                Fn--;
                continue;
            }else{
                if (field[Fn - 1][Fm] == -1) {
                    points.add("S");
                    flag2 = true;
                    break;
                }else {
                    top = false;
                }
            }
        }else{
            if ((field[field.length-1][Fm] == (field[field.length-nRows][Fm] - 1)) & (field[field.length-1][Fm] != 0)) {
                points.add("S");
                Fn = (short) (field.length-1);
            }else{
                if (field[field.length-1][Fm] == -1) {
                    points.add("S");
                    flag2 = true;
                    break;
                }else {
                    top = false;
                }
            }
        }

        if(!left & !right & !top & !bottom){
            break;
        }

    }

    if (flag | flag2) {
        for (short y = 1; y <= points.size(); y++) {
            System.out.print(points.get(points.size() - y));
        }
    }else{
        System.out.println("-1");
    }

}

Источник: https://ru.stackoverflow.com/questions/1275541/%D0%9D%D0%B5%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B8%D0%BC%D0%BE-%D1%81%D0%BD%D0%B8%D0%B7%D0%B8%D1%82%D1%8C-%D0%BF%D0%BE%D1%82%D1%80%D0%B5%D0%B1%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5-%D0%BF%D0%B0%D0%BC%D1%8F%D1%82%D0%B8

Тебе может это понравится...

Добавить комментарий