Approach 焼きなまし法を使いました。

  • 評価:問題のスコア*10000 + (10000 - 面積最大の色の面積)
    • 問題のスコアを使った場合より、約1%良くなった。(5/29 追記)
  • 近傍:ランダムに経路(進む方向の列)を選んで、2点swap, 1点insert, 複数shuffle, 余分な経路の削除、追加、変更
    • いろいろ試したけど狭い範囲の方が良くて、連続する2点のswapを多く使った。
    • 4方向見て、同じ色が3方向以上ある場合は、色を変化させないようにすると、約10%良くなった(provisional 40点にちょっと届かないくらい、10倍高速化しても50点)。(5/30 追記)
  • 高速化:焼きなましで受理しないときに、「4-Conected Component の状態を巻き戻す」で3倍くらい
    • 前計算系の高速化も試していたけど間に合わなかった。

Example scores:
1) 5.0
2) 19552.0
3) 432.0
4) 11922.0
5) 4.0
6) 34.0
7) 3.0
8) 28.0
9) 50.0
10) 450.0

感想
  • 私が見た一番小さいスコアは2だったけど、上位は1とか出しているんだろうか?
    • スコア1を確認できた。(5/29 追記)
  • 焼きなまし法がうまくいく問題で、焼きなまし法を使って負けるパターンは、
    1. 焼きなまし法よりいい方法があった
      • TSP:3opt + kick, Guided Local Search
      • Vertex Coloring:Tabu Search
      • Graph Golf:GA
      • ...
    2. いい評価関数があった
      • GraphReconstruction
      • ...
    3. いい近傍があった
      • CrystalLighting
      • ...
    4. 高速化で負けた
    5. その他
    だと思うけど、今回はどれだろうか?高速化で負けていると思うけど、大差なのでその他もありえそう。
    • 評価関数だった(5/30 追記)



    Source Code 

    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashMap;
    
    public class DanceFloor {
        private final int N;
        private final int numColors;
        private final int numDancers;
        private final int numSteps;
        private final int[][][] rxcxorderToColors;
        private final int[][] dancerXpointToStep;
    
        private static final int[] dr = { -1, 0, 0, 1, 0, };
        private static final int[] dc = { 0, -1, 1, 0, 0, };
        private final int[][] rxcToCount;
        private final int[][] dancerXstepToRxc;
        private final int[][] dancerXstepToRxc0;
        private final int[][] bestDancerXstepToRxc;
    
        static final XorShift rng = new XorShift(System.nanoTime());
        static final Watch watch = new Watch();
        private SAState sa = new SAState();
        private double score;
        private double bestScore = 1e18;
    
        private FourConnectedComponent[] colorToComponents;
    
        private InitializedIntArray diffCounts;
        private IntSetUseInitializedIntArray changedRNcs;
    
        public DanceFloor(int N, int C, int D, int S, String[][] tileColors, int[][] marks) {
            this.N = N;
            this.numColors = C;
            this.numDancers = D;
            this.numSteps = S;
            this.rxcxorderToColors = new int[N][N][numColors];
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    for (int i = 0; i < numColors; i++) {
                        this.rxcxorderToColors[r][c][i] = tileColors[r][c].charAt(i) - '0';
                    }
                }
            }
            dancerXstepToRxc = new int[numDancers][numSteps + 1];
            dancerXstepToRxc0 = new int[numDancers][numSteps + 1];
            bestDancerXstepToRxc = new int[numDancers][numSteps + 1];
            rxcToCount = new int[N][N];
            this.dancerXpointToStep = new int[numDancers][];
            for (int dancer = 0; dancer < numDancers; dancer++) {
                int numPoints = marks[dancer].length / 3;
                dancerXpointToStep[dancer] = new int[numPoints];
                for (int point = 0; point < numPoints; point++) {
                    int c = marks[dancer][3 * point + 0];
                    int r = marks[dancer][3 * point + 1];
                    int step = marks[dancer][3 * point + 2];
                    dancerXpointToStep[dancer][point] = step;
                    dancerXstepToRxc[dancer][step] = (r << 8) | (c);
                    dancerXstepToRxc0[dancer][step] = (r << 8) | (c);
                }
            }
            colorToComponents = new FourConnectedComponent[numColors];
            for (int color = 0; color < numColors; color++) {
                colorToComponents[color] = new FourConnectedComponent(N);
            }
    
            diffCounts = new InitializedIntArray(0, N * N);
            changedRNcs = new IntSetUseInitializedIntArray(N * N);
    
            Utils.debug("size", N, "Color", C, "Dancer", D, "Step", S, "tileColors.length", tileColors.length, "marks.length", marks.length);
        }
    
        public String[] run() {
            solve();
            return makeSolution();
        }
    
        private void solve() {
            greedy();
            sa.startTemperature = score * 0.001;
            SA();
        }
    
        private void greedy() {
            for (int dancer = 0; dancer < numDancers; dancer++) {
                int numPoints = dancerXpointToStep[dancer].length;
                for (int point = 1; point < numPoints; point++) {
                    int startStep = dancerXpointToStep[dancer][point - 1];
                    int startRxc = dancerXstepToRxc[dancer][startStep];
                    int startR = r(startRxc);
                    int startC = c(startRxc);
    
                    int endStep = dancerXpointToStep[dancer][point];
                    int endRxc = dancerXstepToRxc[dancer][endStep];
                    int endR = r(endRxc);
                    int endC = c(endRxc);
    
                    int r = startR;
                    int c = startC;
                    int step = startStep + 1;
                    int numFreeSteps = (endStep - startStep) - (Math.abs(startR - endR) + Math.abs(startC - endC));
                    for (; step <= startStep + numFreeSteps / 2; step++) {
                        if (Math.abs(startR - endR) < Math.abs(startC - endC)) {
                            if (startR < endR) {
                                if (r - 1 >= 0) {
                                    r--;
                                } else {
                                    break;
                                }
                            } else {
                                if (r + 1 < N) {
                                    r++;
                                } else {
                                    break;
                                }
                            }
                        } else {
                            if (startC < endC) {
                                if (c - 1 >= 0) {
                                    c--;
                                } else {
                                    break;
                                }
                            } else {
                                if (c + 1 < N) {
                                    c++;
                                } else {
                                    break;
                                }
                            }
                        }
                        dancerXstepToRxc[dancer][step] = rxc(r, c);
                        rxcToCount[r][c]++;
                    }
                    for (; step <= endStep; step++) {
                        boolean change = true;
                        if (distance(startR, endC, N / 2, N / 2) < distance(endR, startC, N / 2, N / 2)) {
                            if (r < endR) {
                                r++;
                            } else if (r > endR) {
                                r--;
                            } else if (c < endC) {
                                c++;
                            } else if (c > endC) {
                                c--;
                            } else {
                                if (step + 1 <= endStep) {
                                    if (Math.abs(startR - endR) < Math.abs(startC - endC)) {
                                        if (endR > 0) {
                                            r--;
                                            dancerXstepToRxc[dancer][step] = rxc(r, c);
                                            rxcToCount[r][c]++;
                                            step++;
                                            r++;
                                        } else {
                                            r++;
                                            dancerXstepToRxc[dancer][step] = rxc(r, c);
                                            rxcToCount[r][c]++;
                                            step++;
                                            r--;
                                        }
                                    } else {
                                        if (endC > 0) {
                                            c--;
                                            dancerXstepToRxc[dancer][step] = rxc(r, c);
                                            rxcToCount[r][c]++;
                                            step++;
                                            c++;
                                        } else {
                                            c++;
                                            dancerXstepToRxc[dancer][step] = rxc(r, c);
                                            rxcToCount[r][c]++;
                                            step++;
                                            c--;
                                        }
                                    }
                                } else {
                                    change = false;
                                }
                            }
                        } else {
                            if (c < endC) {
                                c++;
                            } else if (c > endC) {
                                c--;
                            } else if (r < endR) {
                                r++;
                            } else if (r > endR) {
                                r--;
                            } else {
                                if (step + 1 <= endStep) {
                                    if (Math.abs(startR - endR) < Math.abs(startC - endC)) {
                                        if (endR > 0) {
                                            r--;
                                            dancerXstepToRxc[dancer][step] = rxc(r, c);
                                            rxcToCount[r][c]++;
                                            step++;
                                            r++;
                                        } else {
                                            r++;
                                            dancerXstepToRxc[dancer][step] = rxc(r, c);
                                            rxcToCount[r][c]++;
                                            step++;
                                            r--;
                                        }
                                    } else {
                                        if (endC > 0) {
                                            c--;
                                            dancerXstepToRxc[dancer][step] = rxc(r, c);
                                            rxcToCount[r][c]++;
                                            step++;
                                            c++;
                                        } else {
                                            c++;
                                            dancerXstepToRxc[dancer][step] = rxc(r, c);
                                            rxcToCount[r][c]++;
                                            step++;
                                            c--;
                                        }
                                    }
                                } else {
                                    change = false;
                                }
                            }
                        }
                        dancerXstepToRxc[dancer][step] = rxc(r, c);
                        if (change) {
                            rxcToCount[r][c]++;
                        }
                    }
                }
            }
    
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    colorToComponents[getColor(r, c)].add(r, c);
                }
            }
    
            score = calculateScore2();
            Utils.debug("greedy", "score", score, "time", watch.getSecondString());
        }
    
        private int distance(int r, int c, int r2, int c2) {
            return Math.abs(r - r2) + Math.abs(c - c2);
        }
    
        private double calculateScore2() {
            double score = 0;
            int maxArea = 0;
            for (int color = 0; color < numColors; color++) {
                int count = colorToComponents[color].numComponents();
                int area = colorToComponents[color].area();
                score += count * count;
                maxArea = Math.max(maxArea, area);
            }
            return score * 10000 + 10000 - maxArea;
        }
    
        private void SA() {
            double second = (int) watch.getSecond();
            sa.init();
            for (;; ++sa.numIterations) {
                if ((sa.numIterations & ((1 << 8) - 1)) == 0) {
                    sa.update();
    
                    if (sa.isTLE()) {
                        loadBest();
                        Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%4.0f", score), String.format("%4.0f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), "time", watch.getSecondString());
                        break;
                    }
    
                    if (watch.getSecond() > second) {
                        second++;
                        Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), String.format("%4.0f", score), String.format("%4.0f", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), "time", watch.getSecondString());
                    }
                }
    
                mutate();
            }
            Utils.debug("SA", "score", score, "time", watch.getSecondString());
        }
    
        private void mutate() {
            double random = 104 * rng.nextDouble();
            if (random < 1) {
                changePathShuffle();
            } else if (random < 2) {
                changePathInsert();
            } else if (random < 3) {
                changePathStopOrMove();
            } else if (random < 4) {
                changePathSwap();
            } else if (random < 104) {
                changePathSmall();
            }
        }
    
        private void changePathSmall() {
            int dancer = (int) (numDancers * rng.nextDouble());
            int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());
    
            int startStep = dancerXpointToStep[dancer][point];
            int endStep = dancerXpointToStep[dancer][point + 1];
            int numSteps2 = endStep - startStep;
            if (numSteps2 <= 1) {
                return;
            }
    
            int step = startStep + (int) ((numSteps2 - 1) * rng.nextDouble());
            int rxc0 = dancerXstepToRxc[dancer][step];
            int r0 = r(rxc0);
            int c0 = c(rxc0);
    
            assert step + 2 <= endStep;
            int rxc2 = dancerXstepToRxc[dancer][step + 2];
            int r2 = r(rxc2);
            int c2 = c(rxc2);
            int rxc1 = dancerXstepToRxc[dancer][step + 1];
            int r1 = r(rxc1);
            int c1 = c(rxc1);
    
            int direction1 = getDirection(r0, c0, r1, c1);
            int direction2 = getDirection(r1, c1, r2, c2);
            if (direction1 == direction2) {
                return;
            }
    
            int r4 = r0 + dr[direction2];
            int c4 = c0 + dc[direction2];
            if (!isValid(r4, 0, N) || !isValid(c4, 0, N)) {
                return;
            }
            if (direction1 == 4 || direction2 == 4) {
                sa.accept(0);
                dancerXstepToRxc[dancer][step + 1] = rxc(r4, c4);
                dancerXstepToRxc[dancer][step + 2] = rxc(r4 + dr[direction1], c4 + dc[direction1]);
            } else {
    
                for (int color = 0; color < numColors; color++) {
                    colorToComponents[color].save();
                }
    
                colorToComponents[getColor(r1, c1)].remove(r1, c1);
                rxcToCount[r1][c1]--;
                colorToComponents[getColor(r1, c1)].add(r1, c1);
    
                dancerXstepToRxc[dancer][step + 1] = rxc(r4, c4);
    
                colorToComponents[getColor(r4, c4)].remove(r4, c4);
                rxcToCount[r4][c4]++;
                colorToComponents[getColor(r4, c4)].add(r4, c4);
    
                double deltaScore = calculateScore2() - score;
    
                if (sa.accept(deltaScore)) {
                    score += deltaScore;
                    saveBest();
                } else {
                    rxcToCount[r1][c1]++;
                    dancerXstepToRxc[dancer][step + 1] = rxc(r1, c1);
                    rxcToCount[r4][c4]--;
                    for (int color = 0; color < numColors; color++) {
                        colorToComponents[color].load();
                    }
                }
            }
        }
    
        private void changePathSmall0() {
            int dancer = (int) (numDancers * rng.nextDouble());
            int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());
    
            int startStep = dancerXpointToStep[dancer][point];
            int startRxc = dancerXstepToRxc[dancer][startStep];
            int startR = r(startRxc);
            int startC = c(startRxc);
    
            int endStep = dancerXpointToStep[dancer][point + 1];
            int numSteps2 = endStep - startStep;
            if (numSteps2 <= 1) {
                return;
            }
    
            int[] directions = new int[numSteps2];
            for (int step = startStep + 1; step <= endStep; step++) {
                int rxc0 = dancerXstepToRxc[dancer][step - 1];
                int r0 = r(rxc0);
                int c0 = c(rxc0);
    
                int rxc = dancerXstepToRxc[dancer][step];
                int r = r(rxc);
                int c = c(rxc);
    
                int direction = getDirection(r0, c0, r, c);
    
                directions[step - (startStep + 1)] = direction;
            }
    
            int index = (int) ((numSteps2 - 1) * rng.nextDouble());
            if (directions[index] == directions[index + 1]) {
                return;
            }
    
            {
                int swap = directions[index];
                directions[index] = directions[index + 1];
                directions[index + 1] = swap;
            }
    
            for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                r += dr[d];
                c += dc[d];
                if (!isValid(r, 0, N) || !isValid(c, 0, N)) {
                    return;
                }
            }
    
            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].save();
            }
    
            changedRNcs.clear();
            diffCounts.clear();
            for (int step = startStep + 1, r = startR, c = startC, r1 = r(dancerXstepToRxc[dancer][step - 1]), c1 = c(dancerXstepToRxc[dancer][step - 1]); step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                if (d < 4) {
                    r += dr[d];
                    c += dc[d];
                    int rNc = r * N + c;
                    changedRNcs.add(rNc);
                    diffCounts.set(rNc, 1 + diffCounts.get(rNc));
                }
    
                int rxc2 = dancerXstepToRxc[dancer][step];
                int r2 = r(rxc2);
                int c2 = c(rxc2);
                if (getDirection(r1, c1, r2, c2) < 4) {
                    int rNc = r2 * N + c2;
                    changedRNcs.add(rNc);
                    diffCounts.set(rNc, -1 + diffCounts.get(rNc));
                    r1 = r2;
                    c1 = c2;
                }
            }
    
            for (int i = 0; i < changedRNcs.size(); i++) {
                int rNc = changedRNcs.get(i);
                int diffCount = diffCounts.get(rNc);
                if (diffCount == 0) {
                    continue;
                }
                int r = rNc / N;
                int c = rNc % N;
                colorToComponents[getColor(r, c)].remove(r, c);
                rxcToCount[r][c] += diffCount;
                colorToComponents[getColor(r, c)].add(r, c);
            }
    
            double deltaScore = calculateScore2() - score;
    
            if (sa.accept(deltaScore)) {
                score += deltaScore;
    
                for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                    int d = directions[step - (startStep + 1)];
                    r += dr[d];
                    c += dc[d];
                    dancerXstepToRxc[dancer][step] = rxc(r, c);
                }
            } else {
                for (int i = 0; i < changedRNcs.size(); i++) {
                    int rNc = changedRNcs.get(i);
                    int diffCount = diffCounts.get(rNc);
                    if (diffCount == 0) {
                        continue;
                    }
                    int r = rNc / N;
                    int c = rNc % N;
                    rxcToCount[r][c] -= diffCount;
                }
    
                for (int color = 0; color < numColors; color++) {
                    colorToComponents[color].load();
                }
            }
        }
    
        private void changePathShuffle() {
            int dancer = (int) (numDancers * rng.nextDouble());
            int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());
    
            int startStep = dancerXpointToStep[dancer][point];
            int startRxc = dancerXstepToRxc[dancer][startStep];
            int startR = r(startRxc);
            int startC = c(startRxc);
    
            int endStep = dancerXpointToStep[dancer][point + 1];
            int numSteps2 = endStep - startStep;
            if (numSteps2 <= 1) {
                return;
            }
    
            int[] directions = new int[numSteps2];
            for (int step = startStep + 1; step <= endStep; step++) {
                int rxc0 = dancerXstepToRxc[dancer][step - 1];
                int r0 = r(rxc0);
                int c0 = c(rxc0);
    
                int rxc = dancerXstepToRxc[dancer][step];
                int r = r(rxc);
                int c = c(rxc);
    
                int direction = getDirection(r0, c0, r, c);
    
                directions[step - (startStep + 1)] = direction;
            }
    
            int from = (int) ((numSteps2 - 0) * rng.nextDouble());
            int to = (int) ((numSteps2 - 1) * rng.nextDouble());
            if (to >= from) {
                to++;
            }
            if (from > to) {
                int swap = from;
                from = to;
                to = swap;
            }
    
            shuffle(directions, from, to);
    
            for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                r += dr[d];
                c += dc[d];
                if (!isValid(r, 0, N) || !isValid(c, 0, N)) {
                    return;
                }
            }
    
            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].save();
            }
    
            changedRNcs.clear();
            diffCounts.clear();
            for (int step = startStep + 1, r = startR, c = startC, r1 = r(dancerXstepToRxc[dancer][step - 1]), c1 = c(dancerXstepToRxc[dancer][step - 1]); step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                if (d < 4) {
                    r += dr[d];
                    c += dc[d];
                    int rNc = r * N + c;
                    changedRNcs.add(rNc);
                    diffCounts.set(rNc, 1 + diffCounts.get(rNc));
                }
    
                int rxc2 = dancerXstepToRxc[dancer][step];
                int r2 = r(rxc2);
                int c2 = c(rxc2);
                if (getDirection(r1, c1, r2, c2) < 4) {
                    int rNc = r2 * N + c2;
                    changedRNcs.add(rNc);
                    diffCounts.set(rNc, -1 + diffCounts.get(rNc));
                    r1 = r2;
                    c1 = c2;
                }
            }
    
            for (int i = 0; i < changedRNcs.size(); i++) {
                int rNc = changedRNcs.get(i);
                int diffCount = diffCounts.get(rNc);
                if (diffCount == 0) {
                    continue;
                }
                int r = rNc / N;
                int c = rNc % N;
                colorToComponents[getColor(r, c)].remove(r, c);
                rxcToCount[r][c] += diffCount;
                colorToComponents[getColor(r, c)].add(r, c);
            }
    
            double deltaScore = calculateScore2() - score;
    
            if (sa.accept(deltaScore)) {
                score += deltaScore;
    
                for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                    int d = directions[step - (startStep + 1)];
                    r += dr[d];
                    c += dc[d];
                    dancerXstepToRxc[dancer][step] = rxc(r, c);
                }
    
                saveBest();
            } else {
                for (int i = 0; i < changedRNcs.size(); i++) {
                    int rNc = changedRNcs.get(i);
                    int diffCount = diffCounts.get(rNc);
                    if (diffCount == 0) {
                        continue;
                    }
                    int r = rNc / N;
                    int c = rNc % N;
                    rxcToCount[r][c] -= diffCount;
                }
    
                for (int color = 0; color < numColors; color++) {
                    colorToComponents[color].load();
                }
            }
        }
    
        private void changePathInsert() {
            int dancer = (int) (numDancers * rng.nextDouble());
            int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());
    
            int startStep = dancerXpointToStep[dancer][point];
            int startRxc = dancerXstepToRxc[dancer][startStep];
            int startR = r(startRxc);
            int startC = c(startRxc);
    
            int endStep = dancerXpointToStep[dancer][point + 1];
            int numSteps2 = endStep - startStep;
            if (numSteps2 <= 1) {
                return;
            }
    
            int[] directions = new int[numSteps2];
            for (int step = startStep + 1; step <= endStep; step++) {
                int rxc0 = dancerXstepToRxc[dancer][step - 1];
                int r0 = r(rxc0);
                int c0 = c(rxc0);
    
                int rxc = dancerXstepToRxc[dancer][step];
                int r = r(rxc);
                int c = c(rxc);
    
                int direction = getDirection(r0, c0, r, c);
    
                directions[step - (startStep + 1)] = direction;
            }
    
            int from = (int) ((numSteps2 - 0) * rng.nextDouble());
            int to = (int) ((numSteps2 - 1) * rng.nextDouble());
            if (to >= from) {
                to++;
            }
            if (from < to) {
                int direction = directions[from];
                for (int i = from; i < to; i++) {
                    directions[i] = directions[i + 1];
                }
                directions[to] = direction;
            } else {
                int direction = directions[from];
                for (int i = from - 1; i >= to; i--) {
                    directions[i + 1] = directions[i];
                }
                directions[to] = direction;
            }
    
            for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                r += dr[d];
                c += dc[d];
                if (!isValid(r, 0, N) || !isValid(c, 0, N)) {
                    return;
                }
            }
    
            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].save();
            }
    
            changedRNcs.clear();
            diffCounts.clear();
            for (int step = startStep + 1, r = startR, c = startC, r1 = r(dancerXstepToRxc[dancer][step - 1]), c1 = c(dancerXstepToRxc[dancer][step - 1]); step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                if (d < 4) {
                    r += dr[d];
                    c += dc[d];
                    int rNc = r * N + c;
                    changedRNcs.add(rNc);
                    diffCounts.set(rNc, 1 + diffCounts.get(rNc));
                }
    
                int rxc2 = dancerXstepToRxc[dancer][step];
                int r2 = r(rxc2);
                int c2 = c(rxc2);
                if (getDirection(r1, c1, r2, c2) < 4) {
                    int rNc = r2 * N + c2;
                    changedRNcs.add(rNc);
                    diffCounts.set(rNc, -1 + diffCounts.get(rNc));
                    r1 = r2;
                    c1 = c2;
                }
            }
    
            for (int i = 0; i < changedRNcs.size(); i++) {
                int rNc = changedRNcs.get(i);
                int diffCount = diffCounts.get(rNc);
                if (diffCount == 0) {
                    continue;
                }
                int r = rNc / N;
                int c = rNc % N;
                colorToComponents[getColor(r, c)].remove(r, c);
                rxcToCount[r][c] += diffCount;
                colorToComponents[getColor(r, c)].add(r, c);
            }
    
            double deltaScore = calculateScore2() - score;
    
            if (sa.accept(deltaScore)) {
                score += deltaScore;
                for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                    int d = directions[step - (startStep + 1)];
                    r += dr[d];
                    c += dc[d];
                    dancerXstepToRxc[dancer][step] = rxc(r, c);
                }
                saveBest();
            } else {
                for (int i = 0; i < changedRNcs.size(); i++) {
                    int rNc = changedRNcs.get(i);
                    int diffCount = diffCounts.get(rNc);
                    if (diffCount == 0) {
                        continue;
                    }
                    int r = rNc / N;
                    int c = rNc % N;
                    rxcToCount[r][c] -= diffCount;
                }
    
                for (int color = 0; color < numColors; color++) {
                    colorToComponents[color].load();
                }
            }
        }
    
        private void changePathSwap() {
            int dancer = (int) (numDancers * rng.nextDouble());
            int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());
    
            int startStep = dancerXpointToStep[dancer][point];
            int startRxc = dancerXstepToRxc[dancer][startStep];
            int startR = r(startRxc);
            int startC = c(startRxc);
    
            int endStep = dancerXpointToStep[dancer][point + 1];
            int numSteps2 = endStep - startStep;
            if (numSteps2 <= 1) {
                return;
            }
    
            int[] directions = new int[numSteps2];
            for (int step = startStep + 1; step <= endStep; step++) {
                int rxc0 = dancerXstepToRxc[dancer][step - 1];
                int r0 = r(rxc0);
                int c0 = c(rxc0);
    
                int rxc = dancerXstepToRxc[dancer][step];
                int r = r(rxc);
                int c = c(rxc);
    
                int direction = getDirection(r0, c0, r, c);
    
                directions[step - (startStep + 1)] = direction;
            }
    
            int index = (int) ((numSteps2 - 0) * rng.nextDouble());
            while (directions[index] == 4) {
                index = (int) ((numSteps2 - 0) * rng.nextDouble());
            }
            int index2 = -1;
            for (int i = index + 1; i < directions.length; i++) {
                if (directions[i] != 4 && directions[i] != directions[index]) {
                    index2 = i;
                    break;
                }
            }
            if (index2 == -1) {
                return;
            }
    
            {
                int swap = directions[index];
                directions[index] = directions[index2];
                directions[index2] = swap;
            }
    
            for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                r += dr[d];
                c += dc[d];
                if (!isValid(r, 0, N) || !isValid(c, 0, N)) {
                    return;
                }
            }
    
            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].save();
            }
    
            changedRNcs.clear();
            diffCounts.clear();
            for (int step = startStep + 1, r = startR, c = startC, r1 = r(dancerXstepToRxc[dancer][step - 1]), c1 = c(dancerXstepToRxc[dancer][step - 1]); step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                if (d < 4) {
                    r += dr[d];
                    c += dc[d];
                    int rNc = r * N + c;
                    changedRNcs.add(rNc);
                    diffCounts.set(rNc, 1 + diffCounts.get(rNc));
                }
    
                int rxc2 = dancerXstepToRxc[dancer][step];
                int r2 = r(rxc2);
                int c2 = c(rxc2);
                if (getDirection(r1, c1, r2, c2) < 4) {
                    int rNc = r2 * N + c2;
                    changedRNcs.add(rNc);
                    diffCounts.set(rNc, -1 + diffCounts.get(rNc));
                    r1 = r2;
                    c1 = c2;
                }
            }
    
            for (int i = 0; i < changedRNcs.size(); i++) {
                int rNc = changedRNcs.get(i);
                int diffCount = diffCounts.get(rNc);
                if (diffCount == 0) {
                    continue;
                }
                int r = rNc / N;
                int c = rNc % N;
                colorToComponents[getColor(r, c)].remove(r, c);
                rxcToCount[r][c] += diffCount;
                colorToComponents[getColor(r, c)].add(r, c);
            }
    
            double deltaScore = calculateScore2() - score;
    
            if (sa.accept(deltaScore)) {
                score += deltaScore;
                for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                    int d = directions[step - (startStep + 1)];
                    r += dr[d];
                    c += dc[d];
                    dancerXstepToRxc[dancer][step] = rxc(r, c);
                }
                saveBest();
            } else {
                for (int i = 0; i < changedRNcs.size(); i++) {
                    int rNc = changedRNcs.get(i);
                    int diffCount = diffCounts.get(rNc);
                    if (diffCount == 0) {
                        continue;
                    }
                    int r = rNc / N;
                    int c = rNc % N;
                    rxcToCount[r][c] -= diffCount;
                }
    
                for (int color = 0; color < numColors; color++) {
                    colorToComponents[color].load();
                }
            }
        }
    
        private void changePathStopOrMove() {
            int dancer = (int) (numDancers * rng.nextDouble());
            int point = (int) ((dancerXpointToStep[dancer].length - 1) * rng.nextDouble());
    
            int startStep = dancerXpointToStep[dancer][point];
            int startRxc = dancerXstepToRxc[dancer][startStep];
            int startR = r(startRxc);
            int startC = c(startRxc);
    
            int endStep = dancerXpointToStep[dancer][point + 1];
            int endRxc = dancerXstepToRxc[dancer][endStep];
            int endR = r(endRxc);
            int endC = c(endRxc);
    
            int numSteps2 = endStep - startStep;
            if (numSteps2 <= 1) {
                return;
            }
    
            int dr1 = endR - startR;
            int dc1 = endC - startC;
            int dr2 = Math.abs(dr1);
            int dc2 = Math.abs(dc1);
            int shortestPath = dr2 + dc2;
            if (numSteps2 - shortestPath <= 1) {
                return;
            }
            int[] directions = new int[numSteps2];
            int[] counts = new int[5];
            IntList[] indexes = new IntList[5];
            for (int i = 0; i < indexes.length; i++) {
                indexes[i] = new IntList(numSteps2);
            }
            if (dr1 > 0) {
                counts[3] -= dr2;
            } else if (dr1 < 0) {
                counts[0] -= dr2;
            }
            if (dc1 > 0) {
                counts[2] -= dc2;
            } else if (dc1 < 0) {
                counts[1] -= dc2;
            }
            for (int step = startStep + 1; step <= endStep; step++) {
                int rxc0 = dancerXstepToRxc[dancer][step - 1];
                int r0 = r(rxc0);
                int c0 = c(rxc0);
    
                int rxc = dancerXstepToRxc[dancer][step];
                int r = r(rxc);
                int c = c(rxc);
    
                int direction = getDirection(r0, c0, r, c);
    
                directions[step - (startStep + 1)] = direction;
                counts[direction]++;
                indexes[direction].add(step - (startStep + 1));
            }
            int index = (int) (counts.length * rng.nextDouble());
            while ((index < 4 && counts[index] <= 0) || (index == 4 && counts[index] <= 1)) {
                index = (int) (counts.length * rng.nextDouble());
            }
    
            if (index == 4) {
                assert indexes[4].size() >= 2;
                int index2 = (int) ((indexes[4].size() - 1) * rng.nextDouble());
                int i2 = indexes[4].get(index2);
                int i3 = indexes[4].get(index2 + 1);
    
                assert directions[i2] == 4;
                assert directions[i3] == 4;
                double random = rng.nextDouble();
                if (random < 0.25) {
                    directions[i2] = 1;
                    directions[i3] = 2;
                } else if (random < 0.5) {
                    directions[i2] = 2;
                    directions[i3] = 1;
                } else if (random < 0.75) {
                    directions[i2] = 0;
                    directions[i3] = 3;
                } else {
                    directions[i2] = 3;
                    directions[i3] = 0;
                }
            } else if (index == 0 || index == 3) {
                assert indexes[0].size() >= 1;
                assert indexes[3].size() >= 1;
                int i2 = indexes[0].get((int) (indexes[0].size() * rng.nextDouble()));
                int i3 = -1;
                {
                    int min = (int) 1e9;
                    for (int i = 0; i < indexes[3].size(); i++) {
                        int abs = Math.abs(indexes[3].get(i) - i2);
                        if (abs < min) {
                            min = abs;
                            i3 = indexes[3].get(i);
                        } else {
                            break;
                        }
                    }
                }
    
                assert directions[i2] == 0;
                assert directions[i3] == 3;
                double random = rng.nextDouble();
                if (random < 0.333) {
                    directions[i2] = 4;
                    directions[i3] = 4;
                } else if (random < 0.666) {
                    directions[i2] = 1;
                    directions[i3] = 2;
                } else {
                    directions[i2] = 2;
                    directions[i3] = 1;
                }
    
            } else {
                assert indexes[1].size() >= 1;
                assert indexes[2].size() >= 1;
                int i2 = indexes[1].get((int) (indexes[1].size() * rng.nextDouble()));
                int i3 = -1;
                {
                    int min = (int) 1e9;
                    for (int i = 0; i < indexes[2].size(); i++) {
                        int abs = Math.abs(indexes[2].get(i) - i2);
                        if (abs < min) {
                            min = abs;
                            i3 = indexes[2].get(i);
                        } else {
                            break;
                        }
                    }
                }
    
                assert directions[i2] == 1;
                assert directions[i3] == 2;
                double random = rng.nextDouble();
                if (random < 0.333) {
                    directions[i2] = 4;
                    directions[i3] = 4;
                } else if (random < 0.666) {
                    directions[i2] = 0;
                    directions[i3] = 3;
                } else {
                    directions[i2] = 3;
                    directions[i3] = 0;
                }
            }
            for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                r += dr[d];
                c += dc[d];
                if (!isValid(r, 0, N) || !isValid(c, 0, N)) {
                    return;
                }
            }
    
            for (int color = 0; color < numColors; color++) {
                colorToComponents[color].save();
            }
    
            changedRNcs.clear();
            diffCounts.clear();
            for (int step = startStep + 1, r = startR, c = startC, r1 = r(dancerXstepToRxc[dancer][step - 1]), c1 = c(dancerXstepToRxc[dancer][step - 1]); step <= endStep; step++) {
                int d = directions[step - (startStep + 1)];
                if (d < 4) {
                    r += dr[d];
                    c += dc[d];
                    int rNc = r * N + c;
                    changedRNcs.add(rNc);
                    diffCounts.set(rNc, 1 + diffCounts.get(rNc));
                }
    
                int rxc2 = dancerXstepToRxc[dancer][step];
                int r2 = r(rxc2);
                int c2 = c(rxc2);
                if (getDirection(r1, c1, r2, c2) < 4) {
                    int rNc = r2 * N + c2;
                    changedRNcs.add(rNc);
                    diffCounts.set(rNc, -1 + diffCounts.get(rNc));
                    r1 = r2;
                    c1 = c2;
                }
            }
    
            for (int i = 0; i < changedRNcs.size(); i++) {
                int rNc = changedRNcs.get(i);
                int diffCount = diffCounts.get(rNc);
                if (diffCount == 0) {
                    continue;
                }
                int r = rNc / N;
                int c = rNc % N;
                colorToComponents[getColor(r, c)].remove(r, c);
                rxcToCount[r][c] += diffCount;
                colorToComponents[getColor(r, c)].add(r, c);
            }
    
            double deltaScore = calculateScore2() - score;
    
            if (sa.accept(deltaScore)) {
                score += deltaScore;
    
                for (int step = startStep + 1, r = startR, c = startC; step <= endStep; step++) {
                    int d = directions[step - (startStep + 1)];
                    r += dr[d];
                    c += dc[d];
                    dancerXstepToRxc[dancer][step] = rxc(r, c);
                }
                saveBest();
            } else {
                for (int i = 0; i < changedRNcs.size(); i++) {
                    int rNc = changedRNcs.get(i);
                    int diffCount = diffCounts.get(rNc);
                    if (diffCount == 0) {
                        continue;
                    }
                    int r = rNc / N;
                    int c = rNc % N;
                    rxcToCount[r][c] -= diffCount;
                }
    
                for (int color = 0; color < numColors; color++) {
                    colorToComponents[color].load();
                }
            }
        }
    
        private void saveBest() {
            if (score < bestScore) {
                bestScore = score;
                for (int dancer = 0; dancer < numDancers; dancer++) {
                    for (int step = 0; step < numSteps; step++) {
                        bestDancerXstepToRxc[dancer][step] = dancerXstepToRxc[dancer][step];
                    }
                }
            }
        }
    
        private void loadBest() {
            score = bestScore;
            for (int dancer = 0; dancer < numDancers; dancer++) {
                for (int step = 0; step < numSteps; step++) {
                    dancerXstepToRxc[dancer][step] = bestDancerXstepToRxc[dancer][step];
                }
            }
        }
    
        private String[] makeSolution() {
            StringBuilder[] sbs = new StringBuilder[numSteps];
            for (int step = 0; step < numSteps; step++) {
                sbs[step] = new StringBuilder();
            }
            for (int dancer = 0; dancer < numDancers; dancer++) {
                for (int step = 0; step < numSteps; step++) {
                    int rxc = dancerXstepToRxc[dancer][step];
                    int r = r(rxc);
                    int c = c(rxc);
    
                    int rxc1 = dancerXstepToRxc[dancer][step + 1];
                    int r1 = r(rxc1);
                    int c1 = c(rxc1);
    
                    if (c1 > c) {
                        sbs[step].append('R');
                    } else if (c1 < c) {
                        sbs[step].append('L');
                    } else if (r1 > r) {
                        sbs[step].append('D');
                    } else if (r1 < r) {
                        sbs[step].append('U');
                    } else {
                        sbs[step].append('-');
                    }
    
                }
            }
            String[] ret = new String[numSteps];
            for (int step = 0; step < numSteps; step++) {
                ret[step] = sbs[step].toString();
            }
            return ret;
        }
    
        private int getColor(int r, int c) {
            return rxcxorderToColors[r][c][rxcToCount[r][c] % numColors];
        }
    
        private boolean isValid(int v, int min, int minUpper) {
            return v >= min && v < minUpper;
        }
    
        private int rxc(int r, int c) {
            return (r << 8) | c;
        }
    
        private static final int r(int v) {
            return (v >>> 8) & 255;
        }
    
        private static final int c(int v) {
            return v & 255;
        }
    
        private int getDirection(int fromR, int fromC, int toR, int toC) {
            if (toR < fromR) {
                return 0;
            }
            if (toR > fromR) {
                return 3;
            }
            if (toC < fromC) {
                return 1;
            }
            if (toC > fromC) {
                return 2;
            }
            return 4;
        }
    
        private void shuffle(int[] a) {
            for (int i = a.length - 1; i >= 0; i--) {
                int j = (int) ((i + 1) * rng.nextDouble());
                swap(a, i, j);
            }
        }
    
        private void shuffle(int[] a, int l, int r) {
            for (int i = r; i >= l; i--) {
                int j = l + (int) ((i + 1 - l) * rng.nextDouble());
                swap(a, i, j);
            }
        }
    
        private void swap(int[] a, int i, int j) {
            int swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }
    
        public static void main(String[] args) {
            try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    
                int N = Integer.parseInt(br.readLine());
                int C = Integer.parseInt(br.readLine());
                int D = Integer.parseInt(br.readLine());
                int S = Integer.parseInt(br.readLine());
    
                String[][] tileColors = new String[N][N];
                for (int y = 0; y < N; y++) {
                    for (int x = 0; x < N; x++) {
                        tileColors[y][x] = br.readLine();
                    }
                }
    
                int[][] marks = new int[D][];
                for (int i = 0; i < D; i++) {
                    int numMarks = Integer.parseInt(br.readLine());
                    marks[i] = new int[3 * numMarks];
                    String[] s = br.readLine().split(" ");
                    for (int j = 0; j < 3 * numMarks; j++) {
                        marks[i][j] = Integer.parseInt(s[j]);
                    }
                }
    
                String[] ret = new DanceFloor(N, C, D, S, tileColors, marks).run();
    
                System.out.println(ret.length);
                for (int i = 0; i < ret.length; i++) {
                    System.out.println(ret[i]);
                }
                System.out.flush();
    
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
    
    class InitializedIntArray {
        private int[] values;
        private int initialValue;
        private int[] versions;
        private int latestVersion;
    
        public InitializedIntArray(int initial_value, int size) {
            init(initial_value, size);
        }
    
        public void init(int initial_value, int size) {
            this.initialValue = initial_value;
            values = new int[size];
            versions = new int[size];
            latestVersion = 1;
        }
    
        void clear() {
            latestVersion++;
        }
    
        public int get(int index) {
            assert (index < values.length);
            if (versions[index] != latestVersion) {
                versions[index] = latestVersion;
                values[index] = initialValue;
            }
            return values[index];
        }
    
        public void set(int index, int value) {
            assert (index < values.length);
            versions[index] = latestVersion;
            values[index] = value;
        }
    }
    
    class SAState {
    
        public static final boolean useTime = true;
    
        public double startTime = 0;
        public double endTime = 9.5;
        public double time = startTime;
        public double startTemperature = 100;
        public double endTemperature = 1e-9;
        public double inverseTemperature = 1.0 / startTemperature;
        public double lastAcceptTemperature = startTemperature;
    
        public double startRange = 700;
        public double endRange = 1;
        public double range = startRange;
    
        public int numIterations;
        public int validIterations;
        public int acceptIterations;
    
        private static final double[] log = new double[32768];
        static {
            for (int i = 0; i < log.length; i++) {
                log[i] = Math.log((i + 0.5) / log.length);
            }
        }
    
        public void init() {
            numIterations = 0;
            validIterations = 0;
            acceptIterations = 0;
    
            startTime = useTime ? DanceFloor.watch.getSecond() : numIterations;
    
            update();
            lastAcceptTemperature = inverseTemperature;
        }
    
        public void update() {
            updateTime();
            updateTemperature();
        }
    
        public void updateTemperature() {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double temperature = interpolate(startY, endY, time0to1);
            inverseTemperature = 1.0 / temperature;
        }
    
        private double elapsedPercentage(double min, double max, double v) {
            return (v - min) / (max - min);
        }
    
        private double interpolate(double v0, double v1, double d0to1) {
            return v0 + (v1 - v0) * d0to1;
        }
    
        public void updateRange() {
            range = endRange + (startRange - endRange) * Math.pow((endTime - time) / (endTime - startTime), 1.0);
        }
    
        public void updateTime() {
            time = useTime ? DanceFloor.watch.getSecond() : numIterations;
        }
    
        public boolean isTLE() {
            return time >= endTime;
        }
    
        public boolean accept(double deltaScore) {
            return acceptS(deltaScore);
        }
    
        public boolean acceptB(double deltaScore) {
            validIterations++;
    
            if (deltaScore > -1e-9) {
                acceptIterations++;
                return true;
            }
    
            assert deltaScore < 0 : Utils.toString(deltaScore);
            assert 1.0 / inverseTemperature >= 0;
    
            double d = deltaScore * inverseTemperature;
            if (d < -10) {
                return false;
            }
            if (log[DanceFloor.rng.nextInt() & 32767] < d) {
                acceptIterations++;
                lastAcceptTemperature = inverseTemperature;
                return true;
            }
            return false;
        }
    
        public boolean acceptS(double deltaScore) {
            validIterations++;
    
            if (deltaScore < 1e-9) {
                acceptIterations++;
                return true;
            }
    
            assert deltaScore > 0;
            assert 1.0 / inverseTemperature >= 0;
    
            double d = -deltaScore * inverseTemperature;
            if (d < -10) {
                return false;
            }
            if (log[DanceFloor.rng.nextInt() & 32767] < d) {
                acceptIterations++;
                lastAcceptTemperature = inverseTemperature;
                return true;
            }
            return false;
        }
    
    }
    
    class FourConnectedComponent {
        private static final int EMPTY = -1;
        private static final int[] dr = { -1, 0, 0, 1, };
        private static final int[] dc = { 0, -1, 1, 0, };
    
        private int[][] board;
        private int numComponents;
        private int N;
        private int id0 = 1;
    
        private int area;
    
        public FourConnectedComponent(int N) {
            this.N = N;
            board = new int[N][N];
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    board[r][c] = EMPTY;
                }
            }
        }
    
        public int area() {
            return area;
        }
    
        private IntSet2 ids = new IntSet2();
    
        public void add(int r, int c) {
            assert board[r][c] == EMPTY;
    
            ids.clear();
            for (int d = 0; d < dr.length; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (!isValid(nr, 0, N) || !isValid(nc, 0, N)) {
                    continue;
                }
                int id = board[nr][nc];
                if (id != EMPTY) {
                    ids.add(id);
                }
            }
    
            if (ids.size() == 0) {
                changes.add((r << 8) | c);
                changes.add(board[r][c]);
                board[r][c] = id0++;
                numComponents++;
            } else if (ids.size() == 1) {
                changes.add((r << 8) | c);
                changes.add(board[r][c]);
                int id = ids.get(0);
                board[r][c] = id;
            } else if (ids.size() >= 2) {
                int id = ids.get(0);
                dfsAdd(r, c, id);
                numComponents -= ids.size() - 1;
            }
    
            area++;
        }
    
        private void dfsAdd(int r, int c, int id) {
            changes.add((r << 8) | c);
            changes.add(board[r][c]);
            board[r][c] = id;
            for (int d = 0; d < dr.length; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (!isValid(nr, 0, N) || !isValid(nc, 0, N)) {
                    continue;
                }
                if (board[nr][nc] == EMPTY) {
                    continue;
                }
                if (board[nr][nc] == id) {
                    continue;
                }
                dfsAdd(nr, nc, id);
            }
        }
    
        private boolean isValid(int v, int min, int minUpper) {
            return v >= min && v < minUpper;
        }
    
        public void remove(int r, int c) {
            int id = board[r][c];
            assert id != EMPTY;
            changes.add((r << 8) | c);
            changes.add(id);
            board[r][c] = EMPTY;
    
            IntSet2 rxcs = ids;
            rxcs.clear();
            for (int d = 0; d < dr.length; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (!isValid(nr, 0, N) || !isValid(nc, 0, N)) {
                    continue;
                }
                if (board[nr][nc] == EMPTY) {
                    continue;
                }
                int nid = board[nr][nc];
                if (nid == id) {
                    rxcs.add(nr * N + nc);
                }
            }
    
            if (rxcs.size() == 0) {
                numComponents--;
            } else if (rxcs.size() == 1) {
            } else if (rxcs.size() >= 2) {
                int count = 0;
                for (; rxcs.size() > 0; count++) {
                    int rxc = rxcs.get(0);
                    int r2 = rxc / N;
                    int c2 = rxc % N;
                    dfsRemove(r2, c2, id0++, rxcs);
                }
                numComponents += count - 1;
            }
    
            area--;
        }
    
        private void dfsRemove(int r, int c, int id, IntSet2 rxcs) {
            rxcs.removeValue(r * N + c);
            changes.add((r << 8) | c);
            changes.add(board[r][c]);
            board[r][c] = id;
            for (int d = 0; d < dr.length; d++) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (!isValid(nr, 0, N) || !isValid(nc, 0, N)) {
                    continue;
                }
                if (board[nr][nc] == EMPTY) {
                    continue;
                }
                if (board[nr][nc] == id) {
                    continue;
                }
                dfsRemove(nr, nc, id, rxcs);
            }
        }
    
        public int numComponents() {
            return numComponents;
        }
    
        private IntList changes = new IntList(1 << 20);
        private int numComponents0;
        private int area0;
    
        public void save() {
            changes.clear();
            numComponents0 = numComponents;
            area0 = area;
        }
    
        public void load() {
            numComponents = numComponents0;
            area = area0;
            for (int i = changes.size() - 1; i >= 0; i -= 2) {
                int v = changes.get(i - 1);
                int r = r(v);
                int c = c(v);
                int value = changes.get(i);
                board[r][c] = value;
            }
        }
    
        private int r(int v) {
            return (v >>> 8) & 255;
        }
    
        private int c(int v) {
            return v & 255;
        }
    }
    
    class IntList {
        private static final int EMPTY = -1;
        private int[] values;
        private int size;
    
        public IntList(int capacity) {
            values = new int[capacity];
            clear();
        }
    
        public void clear() {
            size = 0;
        }
    
        public int size() {
            return size;
        }
    
        public boolean isEmpty() {
            return size() <= 0;
        }
    
        public boolean contains(int value) {
            return indexOf(value) != EMPTY;
        }
    
        public boolean add(int value) {
            values[size++] = value;
            return true;
        }
    
        public boolean removeValue(int value) {
            int index = indexOf(value);
            if (index == EMPTY) {
                return false;
            }
            remove(index);
            return true;
        }
    
        public int remove(int index) {
            int value = values[index];
            for (int i = index; i + 1 < size; i++) {
                values[i] = values[i + 1];
            }
            size--;
            return value;
        }
    
        public int removeFast(int index) {
            int value = values[index];
            values[index] = values[size - 1];
            size--;
            return value;
        }
    
        public int get(int index) {
            return values[index];
        }
    
        public int set(int index, int value) {
            int oldValue = values[index];
            values[index] = value;
            return oldValue;
        }
    
        public void add(int index, int value) {
            assert index <= size;
            for (int i = size - 1; i >= index; i--) {
                values[i + 1] = values[i];
            }
            size++;
            values[index] = value;
        }
    
        public int indexOf(int value) {
            for (int i = 0; i < size; i++) {
                if (values[i] == value) {
                    return i;
                }
            }
            return EMPTY;
        }
    
        public int lastIndexOf(int value) {
            for (int i = size - 1; i >= 0; i--) {
                if (values[i] == value) {
                    return i;
                }
            }
            return EMPTY;
        }
    
    }
    
    class IntSet2 {
        private static final int EMPTY = -1;
        private ArrayList indexToValue;
        private HashMap valueToIndex;
    
        public IntSet2() {
            indexToValue = new ArrayList<>();
            valueToIndex = new HashMap<>();
        }
    
        public boolean add(Integer value) {
            if (valueToIndex.get(value) != null) {
                return false;
            }
            Integer size = Integer.valueOf(indexToValue.size());
            indexToValue.add(value);
            if (valueToIndex.containsKey(value)) {
                valueToIndex.replace(value, size);
            } else {
                valueToIndex.put(value, size);
            }
            return true;
        }
    
        public boolean remove(int index) {
            if (size() == 0) {
                return false;
            }
            assert index < size();
            swap(index, size() - 1);
            Integer remove = indexToValue.remove(size() - 1);
            valueToIndex.remove(remove);
            return true;
        }
    
        public boolean removeValue(Integer value) {
            int index = indexOf(value);
            if (index == EMPTY) {
                return false;
            }
            remove(index);
            return true;
        }
    
        public int get(int index) {
            assert index < size();
            return indexToValue.get(index).intValue();
        }
    
        public int indexOf(Integer value) {
            Integer e = valueToIndex.get(value);
            return e == null ? EMPTY : e.intValue();
        }
    
        public int size() {
            return indexToValue.size();
        }
    
        public boolean isEmpty() {
            return size() <= 0;
        }
    
        public void clear() {
            for (; size() > 0;) {
                remove(0);
            }
        }
    
        public boolean contains(Integer value) {
            return indexOf(value) != EMPTY;
        }
    
        public void swap(int index, int index2) {
            assert index < size();
            assert index2 < size();
    
            {
                Integer swap = indexToValue.get(index);
                indexToValue.set(index, indexToValue.get(index2));
                indexToValue.set(index2, swap);
            }
            if (valueToIndex.containsKey(indexToValue.get(index))) {
                valueToIndex.replace(indexToValue.get(index), index);
            } else {
                valueToIndex.put(indexToValue.get(index), index);
            }
            if (valueToIndex.containsKey(indexToValue.get(index2))) {
                valueToIndex.replace(indexToValue.get(index2), index2);
            } else {
                valueToIndex.put(indexToValue.get(index2), index2);
            }
    
        }
    
    }
    
    final class Utils {
        private Utils() {
        }
    
        public static final void debug(Object... o) {
            System.err.println(toString(o));
        }
    
        public static final String toString(Object... o) {
            return Arrays.deepToString(o);
        }
    
    }
    
    class Watch {
        private long start;
    
        public Watch() {
            init();
        }
    
        public double getSecond() {
            return (System.nanoTime() - start) * 1e-9;
        }
    
        public void init() {
            init(System.nanoTime());
        }
    
        private void init(long start) {
            this.start = start;
        }
    
        public String getSecondString() {
            return toString(getSecond());
        }
    
        public static final String toString(double second) {
            if (second < 60) {
                return String.format("%5.2fs", second);
            } else if (second < 60 * 60) {
                int minute = (int) (second / 60);
                return String.format("%2dm%2ds", minute, (int) (second % 60));
            } else {
                int hour = (int) (second / (60 * 60));
                int minute = (int) (second / 60);
                return String.format("%2dh%2dm%2ds", hour, minute % (60), (int) (second % 60));
            }
        }
    
    }
    
    class XorShift {
        private int w = 88675123;
        private int x = 123456789;
        private int y = 362436069;
        private int z = 521288629;
    
        public XorShift(long l) {
            x = (int) l;
        }
    
        public int nextInt() {
            final int t = x ^ (x << 11);
            x = y;
            y = z;
            z = w;
            w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
            return w;
        }
    
        public long nextLong() {
            return ((long) nextInt() << 32) ^ (long) nextInt();
        }
    
        public double nextDouble() {
            return (nextInt() >>> 1) * 4.6566128730773926E-10;
        }
    
        public int nextInt(int n) {
            return (int) (n * nextDouble());
        }
    
    }
    
    class IntSetUseInitializedIntArray {
        private static final int EMPTY = -1;
        private int size;
        private InitializedIntArray indexToValue;
        private InitializedIntArray valueToIndex;
    
        public IntSetUseInitializedIntArray(int capacity) {
            this.size = 0;
            indexToValue = new InitializedIntArray(0, capacity);
            valueToIndex = new InitializedIntArray(EMPTY, capacity);
        }
    
        public boolean add(int value) {
            if (valueToIndex.get(value) != EMPTY) {
                return false;
            }
            indexToValue.set(size, value);
            valueToIndex.set(indexToValue.get(size), size);
            size++;
            return true;
        }
    
        public boolean remove(int index) {
            if (size == 0) {
                return false;
            }
            assert index < size;
            swap(index, size - 1);
            valueToIndex.set(indexToValue.get(size - 1), EMPTY);
    
            size--;
            return true;
        }
    
        public boolean removeValue(int value) {
            int index = indexOf(value);
            if (index == EMPTY) {
                return false;
            }
            remove(index);
            return true;
        }
    
        public void swap(int index, int index2) {
            assert index < size;
            assert index2 < size;
    
            int swap = indexToValue.get(index);
            indexToValue.set(index, indexToValue.get(index2));
            indexToValue.set(index2, swap);
    
            valueToIndex.set(indexToValue.get(index), index);
            valueToIndex.set(indexToValue.get(index2), index2);
    
        }
    
        public void swapValue(int value, int value2) {
            assert value < size;
            assert value2 < size;
    
            int swap = valueToIndex.get(value);
            valueToIndex.set(value, valueToIndex.get(value2));
            valueToIndex.set(value2, swap);
    
            indexToValue.set(valueToIndex.get(value), value);
            indexToValue.set(valueToIndex.get(value2), value2);
    
        }
    
        public int get(int index) {
            assert index < size;
            return indexToValue.get(index);
        }
    
        public int indexOf(int value) {
            return valueToIndex.get(value);
        }
    
        public int size() {
            return size;
        }
    
        public boolean isEmpty() {
            return size() <= 0;
        }
    
        public void clear() {
            indexToValue.clear();
            valueToIndex.clear();
            size = 0;
        }
    
        public boolean contains(int value) {
            return indexOf(value) != EMPTY;
        }
    
        @Override
        public String toString() {
            int[] copy = new int[size()];
            for (int i = 0; i < copy.length; i++) {
                copy[i] = indexToValue.get(i);
            }
            return Arrays.toString(copy);
        }
    }