将二维数组中的一个模式替换为另一个模式

Question

我正在尝试编写一个执行以下操作的方法：将数组 A 的每次出现替换为数组 B，其中 A 位于二维数组 C 内，然后返回修改后的数组。 A、B 和 C 是二维整数数组。

给定一个矩形数组 c 和另一个矩形数组 a，其中 a 的维度 <= c 的维度，找到与 a 匹配的 c 子数组的第一次出现，并用 b 替换该子数组（必​​须具有与 a) 相同的尺寸。

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;

    }