Заменить шаблон в 2d массиве другим шаблоном

Question

Я пытаюсь написать метод, который выполняет следующие действия: заменяет каждое вхождение массива A на массив B, где A находится внутри двумерного массива C, а затем возвращает измененный массив. A, B и C - двумерные массивы целых чисел.

Для данного прямоугольного массива c и другого прямоугольного массива a с размерами a <= таковыми из c найдите первое вхождение подмассива c, который соответствует a, и замените этот подмассив на b ( которые должны иметь такие же размеры, как а). </p>

public class ReplacePatterns {
    public static void main(String[] args){

    }
    //replace every instance of the pattern a with the pattern b inside c.
    //find a way to get the dimensions of a 2D array
    public static int[][] replacePattern(int[][] a, int[][] b, int[][] c){
        for(int i = 0; i < c.length; i++){
            for(int j = 0; j < c[0].length; j++){
                if(c[i][j] == a[i][j]){ //c[i][j] should match up with a[0][0].
                    int[][] d; //copy the array inside c to d.
                }
            }
        }
    }
}

Answer 1

Итак, если я правильно понял вопрос, вы хотите что-то вроде этого:

public class ReplacePatterns {

    //replace every instance of the pattern a with the pattern b inside c.
    //find a way to get the dimensions of a 2D array
    public static int[][] replace(int[][] a, int[][] b, int[][] c){
        for(int i = 0; i < c.length; i++){
            for(int j = 0; j < c[0].length; j++){
                if(c[i][j] == a[0][0]){ //c[i][j] should match up with a[0][0].
                    // Start verifying the rest of A
                    boolean flag = true;
                    for (int k = 0; k < a.length; k++) {
                        for (int l = 0; l < a[k].length; l++) {
                            if ((i+k) >= c.length || (j+l) >= c[0].length) {
                                flag = false;
                                break;
                            }
                            if (c[i+k][j+l] != a[k][l]) {
                                flag = false;
                            }
                        }
                    }
                    // If all the values for A were exactly the same, then replace it all with whatever is in B
                    if (flag) {
                        for (int k = 0; k < a.length; k++) {
                            for (int l = 0; l < a[k].length; l++) {
                                c[i+k][j+l] = b[k][l];
                            }
                        }
                    }
                }
            }
        }
        return c;
    }

    public static String prettyPrint(int[][] c) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < c.length; i++){
            for(int j = 0; j < c[0].length; j++){
                sb.append("[" + c[i][j] + "]");
            }
            sb.append("\n");
        }
        sb.append("\n");
        return sb.toString();
    }

    public static void test(int[][] patternA, int[][] patternB, int[][] patternC) {
        System.out.println("Pattern A:");
        System.out.println(prettyPrint(patternA));
        System.out.println("Pattern B:");
        System.out.println(prettyPrint(patternB));
        System.out.println("  Array C:");
        System.out.println(prettyPrint(patternC));

        int[][] result = ReplacePatterns.replace(patternA, patternB, patternC);

        System.out.println("  Result:");
        System.out.println(prettyPrint(result));
    }

    public static void main(String[] args){
        int[][] patternA, patternB, patternC;

        System.out.println("Test1:");
        patternA = new int[][]{{1,1}, {1,1}};
        patternB = new int[][]{{3,3}, {3,3}};
        patternC = new int[][]{{0,1,1,1}, {1,1,1,1}, {0,1,1,1}};
        test(patternA, patternB, patternC);

        System.out.println("Test2:");
        patternA = new int[][]{{1,1}, {1,1}};
        patternB = new int[][]{{5,6}, {7,8}};
        patternC = new int[][]{{0,1,1,1,0,1}, {1,1,1,0,1,1,1}, {0,1,1,1,1,1,1}};
        test(patternA, patternB, patternC);
    }
}

Я даже включил там два теста для подтверждения, но я почти уверен, что это будет работать для общего случая. Это, вероятно, неэффективно и может не работать для огромных массивов, но в этом случае оно выполняет свою работу.

Программа выводит графически три заданных шаблона (A, B и C) и распечатывает, как выглядит C после замены. Во втором тестовом прогоне вы должны увидеть что-то вроде этого:

Test2:
Pattern A:
[1][1]
[1][1]


Pattern B:
[5][6]
[7][8]


Array C:
[0][1][1][1][0][1]
[1][1][1][0][1][1]
[0][1][1][1][1][1]


Result:
[0][5][6][1][0][1]
[1][7][8][0][5][6]
[0][1][1][1][7][8]

Answer 2

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

//replace every instance of the pattern a with the pattern b inside c.
    //find a way to get the dimensions of a 2D array
    public int[][] replacePattern(int[][] a, int[][] b, int[][] c) {

        //first make d as copy of array c
        int[][] d = new int[c.length][c[0].length];
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[0].length; j++) {
                d[i][j] = c[i][j];
            }
        }

        //now scan array c for appearance of a. go over every node and on each node initiate a check if the pattern happens at that node
        //note the scan is done as long as we don't step out of array c dimensions
        for (int i = 0; i < c.length - a.length + 1; i++) {
            for (int j = 0; j < c[0].length - a[0].length + 1; j++) {
                //we verify pattern on each node as it can start on each of them
                boolean isPatternOcurring = true;
                for (int m = 0; m < a.length && isPatternOcurring; m++) {
                    for (int n = 0; j < a[0].length; n++) {
                        if (c[i + m][j + n] != a[m][n]) {
                            isPatternOcurring = false;
                            break;
                        }
                    }
                }

                //if pattern occurs, then copy b into d
                if (isPatternOcurring) {
                    for (int m = 0; m < b.length; m++)
                        for (int n = 0; j < b[0].length; n++) 
                            d[i + m][j + n] = b[m][n]; 


                }
            }
        }


        return d;

    }