EvbCFfp1XB

イーブイ進化系 C7BMkOO7Qbmcwck7(AtCoder) dtwYhl0YJqzOnZKi(CodinGame) AnlJ8vIySM8j8Nfq(Codeforces) j8LsXlKzJPRosaXt(Kaggle)

October 2019



Approach 焼きなまし法を使いました。去年の中尾さん高速化をまねしました。
  • 回転させたときに、頂点推移的なグラフだけ使う。(ASPLの計算するときに、すべての頂点から幅優先探索をしなくてよくなる。例えば、180度回転させて同じ形なら、2つのグループに分けれて、幅優先探索する頂点は半分になります。)
  • 並列化して、複数の幅優先探索を同時にやる。
    • やったけど、自分のコンピュータでは高速化の効果は出なかったような...。
  • 1つの幅優先探索を、並列化してやる。
    • やってない。
  • スーパーコンピュータを使う。
    • 使ってない。お休みしてたと思います。


 去年はGrid Graph で Nakano さんとスコアに差があったけど、今年のアプローチでやってみたら、ほとんど同じスコアが出た。
 radeyeさんは、去年の General Graph の 72node 4degree を山登りで最適解出しててさすがだな~と思った。私は去年、焼きなましで結構頑張ったけど最適解だせなくて、今年のアプローチだと一瞬で出て「本当か」ってなった。もしかしたら、内径が大きいほうが良いばあいは存在しません。の例外かな。
 最初圧勝だったけど、最後にほとんど全部逆転されて受賞しなかった。去年できなかったことを今年できるようになってたし、去年はgraph を借りたけど今年は貸せたし、逆転されても僅差だったので、今年のほうが手応えはありました。

追記(10月23日)
 General Graph でグループ数が多いときは、下のコードの IGraph の実装は、全部の頂点を持つ必要がなくて、メモリを節約できたのが楽しかったかも?
 後はこれ、グレタ・トゥーンベリさん(職業 環境少女)ごめんよ。焼きなまし法みたいな時間のかかるアルゴリズムを並列で長時間実行して、ちょっと温暖化させたかも。パソコンから出てくる空気が火傷するかと思うほど熱かったからね。


source code(twitter の gif アニメで使ったやつ)
実行は
Main.main(("thread 1 group 4 graph 3 timelimit 60 print swap swap1 startRate 0.1 endRate 0.1 useMean true useMax false useExp 1").split(" "));
だけど、100万回iteration したら終わりになってるので、timelimitは意味ないね。
import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.UnsupportedEncodingException;
import java.nio.charset.Charset;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

import javax.imageio.IIOImage;
import javax.imageio.ImageIO;
import javax.imageio.ImageWriter;
import javax.imageio.stream.ImageOutputStream;

public class Main {
    private int R;
    private int C;
    private int length;
    private int degree;
    public static final int[] gridR = { 5, 5, 10, 10, 10, 20, 20, 20, 100, 100, 100, 32, };
    public static final int[] gridC = { 5, 10, 10, 10, 10, 20, 20, 20, 100, 100, 100, 32, };
    public static final int[] degrees = { 4, 4, 4, 6, 8, 4, 6, 8, 4, 6, 8, 4, };
    public static final int[] lengthes = { 2, 2, 2, 3, 4, 2, 3, 4, 2, 3, 4, 3, };

    private Graph graph;
    private Graph bestGraph;
    private Graph tmpGraph;

    private int diam;
    private int bestDiam;

    private double aspl;
    private double bestAspl;

    private int invalid;

    static final XorShift rng = new XorShift(System.nanoTime());
    static final Watch watch = new Watch();
    private SAState sa = new SAState();

    private ArrayList<Integer> dr;
    private ArrayList<Integer> dc;

    private IntQueue queue;
    private boolean[] used;
    private boolean[] usedGroup;

    private int numGroups;
    private int numVertexes;
    private int numCenters;

    private int timelimit;
    private boolean useTimer;
    private boolean print;
    private boolean useSwap1;
    private boolean useSwap2;
    private static final TimerManager timer = new TimerManager();

    public static void main(String[] args) {
        Main m = new Main();
        for (int i = 0; i < args.length; i++) {
            if (args[i].equals("thread")) {
                m.numThreads = Integer.parseInt(args[++i]);
            } else if (args[i].equals("group")) {
                m.numGroups = Integer.parseInt(args[++i]);
            } else if (args[i].equals("graph")) {
                int j = Integer.parseInt(args[++i]);
                m.R = m.gridR[j];
                m.C = m.gridC[j];
                m.degree = m.degrees[j];
                m.length = m.lengthes[j];
            } else if (args[i].equals("timelimit")) {
                m.timelimit = Integer.parseInt(args[++i]);
            } else if (args[i].equals("timer")) {
                m.useTimer = true;
            } else if (args[i].equals("print")) {
                m.print = true;
            } else if (args[i].equals("swap")) {
                m.useSwap1 = true;
            } else if (args[i].equals("swap1")) {
                m.useSwap2 = true;
            } else if (args[i].equals("startRate")) {
                m.sa.startRate = Double.parseDouble(args[++i]);
            } else if (args[i].equals("endRate")) {
                m.sa.endRate = Double.parseDouble(args[++i]);
            } else if (args[i].equals("useExp")) {
                m.sa.useExp = Boolean.parseBoolean(args[++i]);
            } else if (args[i].equals("useMean")) {
                m.sa.useMean = Boolean.parseBoolean(args[++i]);
            } else if (args[i].equals("useMax")) {
                m.sa.useMax = Boolean.parseBoolean(args[++i]);
            }
        }
        m.runAGraph();
        if (m.print)
            timer.print();
    }

    private void runAGraph() {
        numVertexes = (R * C) / numGroups;
        numCenters = (R * C) - (numGroups * numVertexes);

        double[] lower_bound_of_diam_aspl = Function.lower_bound_of_diam_aspl(R * C, degree);
        Utils.debug();
        Utils.debug(R + "x" + C, "degree", degree, "length", length, "numGroups", numGroups, "numVertexes", numVertexes, "numCenters", numCenters, "diam", (int) lower_bound_of_diam_aspl[0], "aspl", lower_bound_of_diam_aspl[1]);

        init();
        bestDiam = (int) 1e9;
        bestAspl = 1e9;

        boolean useGreedy = true;
        if (!useGreedy) {
            readSolution();
        }
        if (useGreedy) {
            boolean ok = false;
            if (bestDiam < 1e8 && calculateNumGroups(graph) == numGroups) {
                ok = true;
            }
            if (!ok) {
                clearGraph();
                for (int challenge = 0; challenge < 1e2; challenge++) {
                    if (createRandomGridGraph(numGroups)) {
                        ok = true;
                        break;
                    }
                }
                if (ok) {
                    if (!checkDegree()) {
                        ok = false;
                    }
                    if (calculateNumGroups(graph) != numGroups) {
                        ok = false;
                    }
                }
                if (!ok) {
                    if (print)
                        Utils.debug("fail createRandomGridGraph");
                    return;
                }
            }
        }
        watch.init();
        calculateScore(graph, 1, 1);
        Utils.debug(invalid, diam, aspl, "group", 1, "thread", 1, "time", watch.getSecondString());
        saveBest(false);

        watch.init();
        calculateScore(graph, calculateNumGroups(graph), 1);
        if (print)
            Utils.debug(invalid, diam, aspl, "group", calculateNumGroups(graph), "thread", 1, "time", watch.getSecondString());
        saveBest(false);

        watch.init();
        calculateScore(graph, 1, numThreads);
        if (print)
            Utils.debug(invalid, diam, aspl, "group", 1, "thread", numThreads, "time", watch.getSecondString());
        saveBest(false);

        watch.init();
        calculateScore(graph, calculateNumGroups(graph), numThreads);
        if (print)
            Utils.debug(invalid, diam, aspl, "group", calculateNumGroups(graph), "thread", numThreads, "time", watch.getSecondString());
        saveBest(false);

        loadBest();
        if (R * C < 2000) {
            calculateScore(graph, 1, numThreads);
        } else {
            calculateScore(graph, calculateNumGroups(graph), numThreads);
        }
        if (print)
            Utils.debug(bestDiam, bestAspl);
        if (bestDiam > 1e8) {
            return;
        }
        printDegree();

        watch.init();
        sa.startTime = 0;
        sa.endTime = 1e6;
        for (int j = 0; j < 10; j++) {
            view();
        }
        SA();

        for (int j = 0; j < 20; j++) {
            view();
        }
        Utils.debug("diff diam", bestDiam - lower_bound_of_diam_aspl[0], "diff aspl", bestAspl - lower_bound_of_diam_aspl[1]);

        writeSolution();

        gifWriter.close();

    }

    private int calculateNumGroups(IGraph graph2) {
        if (useTimer)
            timer.start("calculateNumGroups");
        group4: if (R == C) {
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    int node = z(r, c);
                    for (int i = 0; i < graph.degree(node); i++) {
                        int node2 = graph.getNode(node, i);
                        for (int group = 0; group < 4; group++) {
                            int rnode = rotate90(node, group);
                            int rnode2 = rotate90(node2, group);
                            if (!graph.hasEdge(rnode, rnode2)) {
                                break group4;
                            }
                        }
                    }
                }
            }
            if (useTimer)
                timer.stop("calculateNumGroups");
            return 4;
        }
        group2: {
            for (int r = 0; r < R; r++) {
                for (int c = 0; c < C; c++) {
                    int node = z(r, c);
                    for (int i = 0; i < graph.degree(node); i++) {
                        int node2 = graph.getNode(node, i);
                        for (int group = 0; group < 2; group++) {
                            int rnode = rotate180(node, group);
                            int rnode2 = rotate180(node2, group);
                            if (!graph.hasEdge(rnode, rnode2)) {
                                break group2;
                            }
                        }
                    }
                }
            }
            if (useTimer)
                timer.stop("calculateNumGroups");
            return 2;
        }
        if (useTimer)
            timer.stop("calculateNumGroups");
        return 1;
    }

    private boolean createRandomGridGraph(int numGroups) {
        if (useTimer)
            timer.start("createRandomGridGraph");
        graph.clearEdges();
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                int node = z(r, c);
                if (graph.degree(node) > degree) {
                    if (useTimer)
                        timer.stop("createRandomGridGraph");
                    return false;
                }
                if (graph.degree(node) == degree) {
                    continue;
                }
                for (int challenge2 = 0; challenge2 < 10 * degree; challenge2++) {
                    if (graph.degree(node) > degree) {
                        if (useTimer)
                            timer.stop("createRandomGridGraph");
                        return false;
                    }
                    if (graph.degree(node) == degree) {
                        break;
                    }

                    int d = (int) (dr.size() * rng.nextDouble());
                    int nr = r + dr.get(d).intValue();
                    int nc = c + dc.get(d).intValue();
                    if (nr < 0 || nr >= R || nc < 0 || nc >= C) {
                        challenge2--;
                        continue;
                    }
                    int nnode = z(nr, nc);
                    if (graph.hasEdge(node, nnode) || graph.degree(nnode) >= degree) {
                        continue;
                    }
                    if (numGroups == 1) {
                        graph.addEdge(node, nnode);
                    } else if (numGroups == 2) {
                        for (int g = 0; g < numGroups; g++) {
                            int rotate = rotate180(node, g);
                            int nrotate = rotate180(nnode, g);
                            graph.addEdge(rotate, nrotate);
                        }
                    } else if (numGroups == 4) {
                        for (int g = 0; g < numGroups; g++) {
                            int rotate0 = rotate90(node, g);
                            int nrotate0 = rotate90(nnode, g);
                            graph.addEdge(rotate0, nrotate0);
                        }
                    }
                }

                if (graph.degree(node) < degree) {
                    if (useTimer)
                        timer.stop("createRandomGridGraph");
                    return false;
                }

            }
        }

        if (useTimer)
            timer.stop("createRandomGridGraph");
        return true;
    }

    private void writeSolution() {
        if (useTimer)
            timer.start("writeSolution");
        StringBuilder sb = new StringBuilder();
        for (int from = 0; from < R * C; from++) {
            for (int j = 0; j < graph.degree(from); j++) {
                int to = graph.getNode(from, j);
                if (from < to) {
                    sb.append((r(from) + "," + c(from)) + " " + (r(to) + "," + c(to)) + "\n");
                }
            }
        }
        TextFileIO.write(sb.toString(), Paths.get("./out/grid_" + (R + "_x_" + C) + "_d_" + degree + "_l_" + length + "_diam_" + diam + "_aspl_" + aspl + "_g_" + numGroups + "_.edges"));
        if (useTimer)
            timer.stop("writeSolution");
    }

    private void readSolution() {
        if (useTimer)
            timer.start("readSolution");
        File outDir = Paths.get("./out/").toFile();
        ArrayList<File> files = new ArrayList<>();
        for (File file : outDir.listFiles()) {
            files.add(file);
        }
        Collections.shuffle(files);
        for (File file : files) {
            if (!file.isFile()) {
                Utils.debug("continue !file.isFile()");
                continue;
            }
            String name = file.getName();
            String[] split = name.split("_");
            if (split.length != 15) {
                continue;
            }
            if (split[0].equals("grid") && split[2].equals("x") && split[4].equals("d") && split[6].equals("l") && split[8].equals("diam") && split[10].equals("aspl") && split[12].equals("g")) {
            } else {
                continue;
            }
            int r = Integer.parseInt(split[1]);
            int c = Integer.parseInt(split[3]);
            int d = Integer.parseInt(split[5]);
            int l = Integer.parseInt(split[7]);
            int g = Integer.parseInt(split[13]);
            boolean useMod = !true;
            if (r == this.R && c == this.C && d == this.degree && l == this.length && (useMod ? g % this.numGroups == 0 : g == this.numGroups)) {
            } else {
                continue;
            }
            clearGraph();
            for (String line : TextFileIO.readLines(file.toPath(), StandardCharsets.UTF_8)) {
                String[] split2 = line.split("[, ]");
                int fromR = Integer.parseInt(split2[0]);
                int fromC = Integer.parseInt(split2[1]);
                int toR = Integer.parseInt(split2[2]);
                int toC = Integer.parseInt(split2[3]);
                int from = z(fromR, fromC);
                int to = z(toR, toC);
                addEdge(from, to);
            }
            if (R * C < 2000) {
                calculateScore(graph, 1, 1);
            } else {
                calculateScore(graph, calculateNumGroups(graph), 1);
            }
            saveBest(false);
            if (!useMod) {
                if (invalid > 0 || diam > bestDiam || (diam == bestDiam && aspl > bestAspl)) {
                    file.delete();
                }
            }
            loadBest();
            if (R * C < 2000) {
                calculateScore(graph, 1, 1);
            } else {
                calculateScore(graph, calculateNumGroups(graph), 1);
            }
        }

        if (useTimer)
            timer.stop("readSolution");
    }

    private void clearGraph() {
        graph.clearEdges();
    }

    private void init() {

        graph = new Graph(R * C);
        bestGraph = new Graph(R * C);
        tmpGraph = new Graph(R * C);

        this.dr = new ArrayList<>();
        this.dc = new ArrayList<>();
        for (int dr = -length; dr <= length; dr++) {
            int l = length - Math.abs(dr);
            for (int dc = -l; dc <= l; dc++) {
                if (dr == 0 && dc == 0) {
                    continue;
                }
                this.dr.add(dr);
                this.dc.add(dc);
            }
        }

        usedGroup = new boolean[R * C];
        used = new boolean[R * C];
        queue = new IntQueue(R * C + 2);
        maxs = new int[numThreads];
        sums = new double[numThreads];
        invalids = new int[numThreads];
        useds = new boolean[numThreads][R * C];
        queues = new IntQueue[numThreads];
        for (int i = 0; i < numThreads; i++) {
            queues[i] = new IntQueue(R * C + 2);
        }
    }

    private void SA() {
        double second = Math.ceil(watch.getSecond());
        sa.init();
        for (;; sa.numIterations++) {
            if ((sa.numIterations & ((1 << 0) - 1)) == 0) {
                sa.update();
                if (sa.isTLE() || sa.numIterations > 1e5 + sa.lastAcceptIterations) {
                    TextFileIO.appendln(Utils.toString("grid_" + R + "x" + C + "_d_" + degree + "_g_" + numGroups + "_t_" + numThreads + "_sw_" + ((useSwap1 ? 1 : 0) + (useSwap2 ? 2 : 0)) + "_diam_" + (diam) + "_aspl_" + (aspl) + "_i_" + sa.numIterations + "_" + (int) (watch.getSecond()) + "/" + (int) (sa.endTime - sa.startTime + 0.9), getClass().getName()));
                    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("%2d", diam), String.format("%7.5f", aspl), String.format("%2d", bestDiam), String.format("%7.5f", bestAspl), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), sa.startTemperature, sa.endTemperature, R + "x" + C + "_d_" + degree + "_l_" + length + "_g_" + numGroups + "_t_" + numThreads + "_sw_" + ((useSwap1 ? 1 : 0) + (useSwap2 ? 2 : 0)) + "_i_" + sa.numIterations + "_" + (int) (sa.time - sa.startTime + 0.5) + "/" + (int) (sa.endTime - sa.startTime + 0.5));
                    break;
                }
                if (print)
                    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("%2d", diam), String.format("%7.5f", aspl), String.format("%2d", bestDiam), String.format("%7.5f", bestAspl), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature), sa.startTemperature, sa.endTemperature, R + "x" + C + "_d_" + degree + "_l_" + length + "_g_" + numGroups + "_t_" + numThreads + "_sw_" + ((useSwap1 ? 1 : 0) + (useSwap2 ? 2 : 0)) + "_i_" + sa.numIterations + "_" + (int) (sa.time - sa.startTime + 0.5) + "/" + (int) (sa.endTime - sa.startTime + 0.5));
                    }

            }

            mutate();
        }
        Utils.debug("SA", "time", watch.getSecondString());
    }

    private void mutate() {
        if (useSwap1) {
            if (useSwap2) {
                double random = 2 * rng.nextDouble();
                if (random < 1) {
                    swap2();
                } else if (random < 2) {
                    swapNextAndNextNext2();
                }
            } else {
                swap2();
            }
        } else {
            if (useSwap2) {
                swapNextAndNextNext2();
            } else {
                throw new AssertionError();
            }
        }
    }

    private ArrayList<int[]> list = new ArrayList<>();

    private void swapNextAndNextNext2() {
        if (useTimer)
            timer.start("swapNextAndNextNext2");
        list.clear();
        int node0 = (int) (R * C * rng.nextDouble());
        for (int i1 = 0; i1 < graph.degree(node0); i1++) {
            int node1 = graph.getNode(node0, i1);
            assert node1 != node0;
            for (int i2 = 0; i2 < graph.degree(node1); i2++) {
                int node2 = graph.getNode(node1, i2);
                if (node2 == node0 || node2 == node1) {
                    continue;
                }
                if (graph.hasEdge(node0, node2) || graph.hasEdge(node2, node0)) {
                    continue;
                }
                if (length(node0, node2) > length) {
                    continue;
                }
                for (int i3 = 0; i3 < graph.degree(node2); i3++) {
                    int node3 = graph.getNode(node2, i3);
                    if (node3 == node0 || node3 == node1 || node3 == node2) {
                        continue;
                    }
                    if (graph.hasEdge(node1, node3) || graph.hasEdge(node3, node1)) {
                        continue;
                    }
                    if (length(node1, node3) > length) {
                        continue;
                    }
                    list.add(new int[] { node1, node2, node3 });
                }
            }
        }

        if (list.size() == 0) {
            if (useTimer)
                timer.stop("swapNextAndNextNext2");
            return;
        }
        int index = (int) (list.size() * rng.nextDouble());
        int[] nodes = list.get(index);
        int node1 = nodes[0];
        int node2 = nodes[1];
        int node3 = nodes[2];

        saveCurrentGraph();

        if (numGroups == 4) {
            for (int group = 0; group < numGroups; group++) {
                int rotate = group;
                removeEdge(rotate90(node0, rotate), rotate90(node1, rotate));
                removeEdge(rotate90(node2, rotate), rotate90(node3, rotate));
                addEdge(rotate90(node0, rotate), rotate90(node2, rotate));
                addEdge(rotate90(node1, rotate), rotate90(node3, rotate));
            }
        } else if (numGroups == 2 || numGroups == 1) {
            for (int group = 0; group < numGroups; group++) {
                int rotate = group;
                removeEdge(rotate180(node0, rotate), rotate180(node1, rotate));
                removeEdge(rotate180(node2, rotate), rotate180(node3, rotate));
                addEdge(rotate180(node0, rotate), rotate180(node2, rotate));
                addEdge(rotate180(node1, rotate), rotate180(node3, rotate));
            }
        }

        if (!checkDegree() || calculateNumGroups(graph) != numGroups) {
            loadCurrentGraph();
            if (useTimer)
                timer.stop("swapNextAndNextNext2");
            return;
        }

        int currentDiam = diam;
        double currentAspl = aspl;
        int currentInvalid = invalid;
        calculateScore(graph, numGroups, numThreads);
        double deltaScore = (invalid + aspl) - (currentInvalid + currentAspl);

        if (sa.accept(deltaScore)) {
            saveBest();
        } else {
            diam = currentDiam;
            aspl = currentAspl;
            invalid = currentInvalid;
            if (numGroups == 4) {
                for (int group = 0; group < numGroups; group++) {
                    int rotate = group;
                    removeEdge(rotate90(node0, rotate), rotate90(node2, rotate));
                    removeEdge(rotate90(node1, rotate), rotate90(node3, rotate));
                    addEdge(rotate90(node0, rotate), rotate90(node1, rotate));
                    addEdge(rotate90(node2, rotate), rotate90(node3, rotate));
                }
            } else if (numGroups == 2 || numGroups == 1) {
                for (int group = 0; group < numGroups; group++) {
                    int rotate = group;
                    removeEdge(rotate180(node0, rotate), rotate180(node2, rotate));
                    removeEdge(rotate180(node1, rotate), rotate180(node3, rotate));
                    addEdge(rotate180(node0, rotate), rotate180(node1, rotate));
                    addEdge(rotate180(node2, rotate), rotate180(node3, rotate));
                }
            }
        }
        if (useTimer)
            timer.stop("swapNextAndNextNext2");
    }

    private void swap2() {
        if (useTimer)
            timer.start("swap2");
        list.clear();
        int node0 = (int) (R * C * rng.nextDouble());

        for (int d = 0; d < dr.size(); d++) {
            int nr = r(node0) + dr.get(d).intValue();
            int nc = c(node0) + dc.get(d).intValue();
            if (nr < 0 || nr >= R) {
                continue;
            }
            if (nc < 0 || nc >= C) {
                continue;
            }
            int node2 = z(nr, nc);
            if (node2 == node0) {
                continue;
            }
            if (graph.hasEdge(node0, node2) || graph.hasEdge(node2, node0)) {
                continue;
            }
            if (length(node0, node2) > length) {
                continue;
            }

            for (int i1 = 0; i1 < graph.degree(node0); i1++) {
                int node1 = graph.getNode(node0, i1);
                assert node1 != node0;
                if (node1 == node0 || node1 == node2) {
                    continue;
                }

                for (int i3 = 0; i3 < graph.degree(node2); i3++) {
                    int node3 = graph.getNode(node2, i3);
                    if (node3 == node0 || node3 == node1 || node3 == node2) {
                        continue;
                    }
                    if (graph.hasEdge(node1, node3) || graph.hasEdge(node3, node1)) {
                        continue;
                    }
                    if (length(node1, node3) > length) {
                        continue;
                    }
                    list.add(new int[] { node1, node2, node3 });
                }
            }
        }

        if (list.size() == 0) {
            if (useTimer)
                timer.stop("swap2");
            return;
        }
        int index = (int) (list.size() * rng.nextDouble());
        int[] nodes = list.get(index);
        int node1 = nodes[0];
        int node2 = nodes[1];
        int node3 = nodes[2];
        saveCurrentGraph();

        if (numGroups == 4) {
            for (int group = 0; group < numGroups; group++) {
                int rotate = group;
                removeEdge(rotate90(node0, rotate), rotate90(node1, rotate));
                removeEdge(rotate90(node2, rotate), rotate90(node3, rotate));
                addEdge(rotate90(node0, rotate), rotate90(node2, rotate));
                addEdge(rotate90(node1, rotate), rotate90(node3, rotate));
            }
        } else if (numGroups == 2 || numGroups == 1) {
            for (int group = 0; group < numGroups; group++) {
                int rotate = group;
                removeEdge(rotate180(node0, rotate), rotate180(node1, rotate));
                removeEdge(rotate180(node2, rotate), rotate180(node3, rotate));
                addEdge(rotate180(node0, rotate), rotate180(node2, rotate));
                addEdge(rotate180(node1, rotate), rotate180(node3, rotate));
            }
        }

        if (!checkDegree() || calculateNumGroups(graph) != numGroups) {
            loadCurrentGraph();
            if (useTimer)
                timer.stop("swap2");
            return;
        }

        int currentDiam = diam;
        double currentAspl = aspl;
        int currentInvalid = invalid;
        calculateScore(graph, numGroups, numThreads);
        double deltaScore = (invalid + aspl) - (currentInvalid + currentAspl);

        if (sa.accept(deltaScore)) {
            saveBest();
        } else {
            diam = currentDiam;
            aspl = currentAspl;
            invalid = currentInvalid;
            if (numGroups == 4) {
                for (int group = 0; group < numGroups; group++) {
                    int rotate = group;
                    removeEdge(rotate90(node0, rotate), rotate90(node2, rotate));
                    removeEdge(rotate90(node1, rotate), rotate90(node3, rotate));
                    addEdge(rotate90(node0, rotate), rotate90(node1, rotate));
                    addEdge(rotate90(node2, rotate), rotate90(node3, rotate));
                }
            } else if (numGroups == 2 || numGroups == 1) {
                for (int group = 0; group < numGroups; group++) {
                    int rotate = group;
                    removeEdge(rotate180(node0, rotate), rotate180(node2, rotate));
                    removeEdge(rotate180(node1, rotate), rotate180(node3, rotate));
                    addEdge(rotate180(node0, rotate), rotate180(node1, rotate));
                    addEdge(rotate180(node2, rotate), rotate180(node3, rotate));
                }
            }
        }
        if (useTimer)
            timer.stop("swap2");
    }

    private boolean checkDegree() {
        if (useTimer)
            timer.start("checkDegree");
        for (int i = 0; i < R * C; i++) {
            if (graph.degree(i) != degree) {
                if (useTimer)
                    timer.stop("checkDegree");
                return false;
            }
        }
        if (useTimer)
            timer.stop("checkDegree");
        return true;
    }

    private void saveCurrentGraph() {
        if (useTimer)
            timer.start("saveCurrentGraph");
        tmpGraph.copy(graph);
        if (useTimer)
            timer.stop("saveCurrentGraph");
    }

    private void loadCurrentGraph() {
        if (useTimer)
            timer.start("loadCurrentGraph");
        graph.copy(tmpGraph);
        if (useTimer)
            timer.stop("loadCurrentGraph");
    }

    private void calculateScore(IGraph graph, int numGroups, int numThreads) {
        if (numThreads == 1) {
            calculateScore(graph, numGroups);
        } else {
            calculateScoreMultiThreads(graph, numGroups);
        }
    }

    private void calculateScore(IGraph graph, int numGroups) {
        if (useTimer)
            timer.start("calculateScore");
        int RxC = R * C;
        queue.clear();
        Arrays.fill(used, false);
        Arrays.fill(usedGroup, false);

        aspl = 0;
        diam = 0;
        invalid = 0;

        for (int startNode = 0; startNode < RxC; startNode++) {
            if (usedGroup[startNode]) {
                continue;
            }
            int total = 1;
            usedGroup[startNode] = true;
            if (numGroups == 2) {
                if (!usedGroup[rotate180(startNode, 1)]) {
                    total++;
                    usedGroup[rotate180(startNode, 1)] = true;
                }
            } else if (numGroups == 4) {
                for (int rotate = 1; rotate < 4; rotate++) {
                    if (!usedGroup[rotate90(startNode, rotate)]) {
                        total++;
                        usedGroup[rotate90(startNode, rotate)] = true;
                    }
                }
            }

            queue.clear();
            Arrays.fill(used, false);
            {
                queue.add((0 << 16) | (startNode));
                used[startNode] = true;
            }
            for (; !queue.isEmpty();) {
                int v = queue.poll();
                int distance = (v >>> 16) & ((1 << 16) - 1);
                int currentNode = (v >>> 0) & ((1 << 16) - 1);

                diam = Math.max(diam, distance);
                aspl += total * distance;

                if (graph.degree(currentNode) > degree) {
                    invalid += graph.degree(currentNode) - degree;
                }

                for (int i = 0; i < graph.degree(currentNode); i++) {
                    int nextNode = graph.getNode(currentNode, i);
                    if (used[nextNode]) {
                        continue;
                    }

                    if (length(currentNode, nextNode) > length) {
                        invalid += length(currentNode, nextNode) - length;
                    }
                    if (length(currentNode, nextNode) == 0) {
                        invalid++;
                    }

                    used[nextNode] = true;
                    queue.add(((distance + 1) << 16) | (nextNode));
                }
            }

            for (int node = 0; node < RxC; node++) {
                if (!used[node]) {
                    invalid++;
                }
            }

        }
        aspl /= (RxC * RxC - RxC);
        if (useTimer)
            timer.stop("calculateScore");
    }

    private int numThreads;
    private int[] maxs;
    private double[] sums;
    private int[] invalids;
    private IntQueue[] queues;
    private boolean[][] useds;

    private void calculateScoreMultiThreads(IGraph graph, int numGroups) {
        if (useTimer)
            timer.start("calculateScoreMultiThreads");
        Arrays.fill(usedGroup, false);

        Thread[] threads = new Thread[numThreads];
        for (int t = 0; t < numThreads; t++) {
            final int ft = t;
            maxs[ft] = 0;
            sums[ft] = 0;
            invalids[ft] = 0;
            threads[t] = new Thread(new Runnable() {
                @Override
                public void run() {
                    for (int startNode = ft; startNode < R * C; startNode += numThreads) {
                        if (usedGroup[startNode]) {
                            continue;
                        }
                        int total = 1;
                        usedGroup[startNode] = true;
                        if (numGroups == 2) {
                            if (!usedGroup[rotate180(startNode, 1)]) {
                                total++;
                                usedGroup[rotate180(startNode, 1)] = true;
                            }
                        } else if (numGroups == 4) {
                            for (int rotate = 1; rotate < 4; rotate++) {
                                if (!usedGroup[rotate90(startNode, rotate)]) {
                                    total++;
                                    usedGroup[rotate90(startNode, rotate)] = true;
                                }
                            }
                        }

                        queues[ft].clear();
                        Arrays.fill(useds[ft], false);
                        {
                            queues[ft].add((0 << 16) | (startNode));
                            useds[ft][startNode] = true;
                        }
                        for (; !queues[ft].isEmpty();) {
                            int v = queues[ft].poll();
                            int distance = (v >>> 16) & ((1 << 16) - 1);
                            int currentNode = (v >>> 0) & ((1 << 16) - 1);

                            maxs[ft] = Math.max(maxs[ft], distance);
                            sums[ft] += total * distance;

                            if (graph.degree(currentNode) > degree) {
                                invalid += graph.degree(currentNode) - degree;
                            }

                            for (int i = 0; i < graph.degree(currentNode); i++) {
                                int nextNode = graph.getNode(currentNode, i);
                                if (useds[ft][nextNode]) {
                                    continue;
                                }

                                if (length(currentNode, nextNode) > length) {
                                    invalids[ft] += length(currentNode, nextNode) - length;
                                }
                                if (length(currentNode, nextNode) == 0) {
                                    invalids[ft]++;
                                }

                                useds[ft][nextNode] = true;
                                queues[ft].add(((distance + 1) << 16) | (nextNode));
                            }
                        }

                        for (int node = 0; node < R * C; node++) {
                            if (!useds[ft][node]) {
                                invalids[ft]++;
                            }
                        }

                    }
                }
            });
        }

        for (int t = 0; t < numThreads; t++) {
            threads[t].start();
        }
        for (int t = 0; t < numThreads; t++) {
            try {
                threads[t].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        aspl = 0;
        diam = 0;
        this.invalid = 0;
        for (int t = 0; t < numThreads; t++) {
            aspl += (double) sums[t] / (R * C * R * C - R * C);
            diam = Math.max(diam, maxs[t]);
            this.invalid += invalids[t];
        }

        if (useTimer)
            timer.stop("calculateScoreMultiThreads");
    }

    private void saveBest() {
        saveBest(true);
    }

    private void saveBest(boolean print) {
        if (useTimer)
            timer.start("saveBest");
        if (invalid > 0) {
            if (this.print)
                Utils.debug("invalid", invalid);
            if (useTimer)
                timer.stop("saveBest");
            return;
        }
        if (diam < bestDiam || (diam == bestDiam && aspl <= bestAspl)) {
            if (print) {
                if (diam < bestDiam || (diam == bestDiam && aspl < bestAspl)) {
                    TextFileIO.appendln(Utils.toString("grid_" + R + "x" + C + "_d_" + degree + "_g_" + numGroups + "_t_" + numThreads + "_sw_" + ((useSwap1 ? 1 : 0) + (useSwap2 ? 2 : 0)) + "_diam_" + (diam) + "_aspl_" + (aspl) + "_i_" + sa.numIterations + "_" + (int) (sa.time - sa.startTime + 0.5) + "/" + (int) (sa.endTime - sa.startTime + 0.5), getClass().getName()));
                }
            }
            bestDiam = diam;
            bestAspl = aspl;
            bestGraph.copy(graph);
            count = 0;
        }
        view();
        if (useTimer)
            timer.stop("saveBest");
    }

    private void loadBest() {
        if (useTimer)
            timer.start("loadBest");
        diam = bestDiam;
        aspl = bestAspl;
        graph.copy(bestGraph);
        if (useTimer)
            timer.stop("loadBest");
    }

    private void printDegree() {
        if (useTimer)
            timer.start("printDegree");
        if (print)
            for (int i = 0; i < R * C; i++) {
                if (graph.degree(i) != degree) {
                    Utils.debug("ac", sa.acceptIterations, "node", i, "degree", graph.degree(i), "max degree", degree);
                }
            }
        if (useTimer)
            timer.stop("printDegree");
    }

    private void addEdge(int node0, int node1) {
        graph.addEdge(node0, node1);
    }

    private void removeEdge(int node0, int node1) {
        graph.removeEdge(node0, node1);
    }

    private int rotate180(int node, int group) {
        if (group % 2 == 0) {
            return node;
        }
        int r = r(node);
        int c = c(node);
        return z(R - 1 - r, C - 1 - c);
    }

    private int rotate90(int node, int group) {
        assert R == C;
        int r = r(node);
        int c = c(node);
        for (int i = 0; i < group; i++) {
            int nr = R - 1 - c;
            int nc = r;
            r = nr;
            c = nc;
        }
        return z(r, c);
    }

    private int length(int z, int z2) {
        return Math.abs(r(z2) - r(z)) + Math.abs(c(z2) - c(z));
    }

    private int z(int r, int c) {
        return r * C + c;
    }

    private int r(int z) {
        return z / C;
    }

    private int c(int z) {
        return z % C;
    }

    private GifWriter gifWriter = new GifWriter("./out/anime.gif");

    private int max = 32;
    private int count = 0;

    private void view() {
        if (count >= max) {
            if (count == max) {
                max = Math.max(1, max / 2);
            }
//            count = 0;
            return;
        }
        count++;

        int height = 512;
        int width = 512;
        int height2 = 30 + height;
        int width2 = 30 + width;
        BufferedImage bi = new BufferedImage(width2, height2, BufferedImage.TYPE_INT_RGB);
        Graphics2D g2 = (Graphics2D) bi.getGraphics();
        g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
        g2.setColor(new Color(0xDDDDDD));
        g2.fillRect(0, 0, width2, height2);

        g2.setColor(Color.WHITE);
        g2.fillRect(15, 15, width, height);

        int sizeR = height / R;
        int sizeC = width / C;
        int[] rToSizeC2 = new int[sizeC];
        for (int i = 0; i < rToSizeC2.length; i++) {
            rToSizeC2[i] = sizeC / (i + 1);
        }

        for (int from = 0; from < R * C; from++) {
            for (int j = 0; j < graph.degree(from); j++) {
                int to = graph.getNode(from, j);
                if (from >= to) {
                    continue;
                }
                g2.setColor(Color.LIGHT_GRAY);
                g2.drawLine(15 + sizeC / 2 + sizeC * (from % C), 15 + sizeR / 2 + sizeR * (from / C), 15 + sizeC / 2 + sizeC * (to % C), 15 + sizeR / 2 + sizeR * (to / C));
            }
        }
        g2.setColor(Color.GREEN);
        for (int from = 0; from < R * C; from++) {
            g2.drawOval(15 + sizeC / 2 + sizeC * (from % C) - 2, 15 + sizeR / 2 + sizeR * (from / C) - 2, 4, 4);
            g2.fillOval(15 + sizeC / 2 + sizeC * (from % C) - 2, 15 + sizeR / 2 + sizeR * (from / C) - 2, 4, 4);
        }

        int x = 30;
        int y = 30;

        g2.setColor(Color.BLACK);
        g2.drawString("Diam : " + diam, x, y += 15);
        g2.drawString("ASPL : " + aspl, x, y += 15);

        gifWriter.add(bi);

    }
}

class SAState {

    public static final boolean useTime = !true;

    public double startTime = 0;
    public double endTime = 1e6;
    public double time = startTime;

    public double startTemperature = 40;
    public double endTemperature = 1e9;
    public double expTemperature = 1;
    public double inverseTemperature = 1.0 / startTemperature;
    public double lastAcceptTemperature = startTemperature;

    public double startRange = 101;
    public double endRange = 3;
    public double range = startRange;

    public int numIterations;
    public int validIterations;
    public int acceptIterations;
    public int lastAcceptIterations;

    private double minAbsDeltaScore;
    private double maxAbsDeltaScore;
    private MeanHelper helper = new MeanHelper();

    public void init() {
        numIterations = 0;
        validIterations = 0;
        acceptIterations = 0;

        minAbsDeltaScore = 1e99;
        maxAbsDeltaScore = 1e-99;
        helper.clear();

        startTime = useTime ? Main.watch.getSecond() : numIterations;

        update();
        lastAcceptTemperature = inverseTemperature;
    }

    public void update() {
        updateTime();
        updateTemperature();
        updateRange();
    }

    public boolean useMean = true;
    public boolean useMax = !true;
    public double startRate = 0.5;
    public double endRate = 0.1;
    public boolean useExp = true;

    public void updateStartTemperature() {
        if (useMean) {
            double d = helper.mean(maxAbsDeltaScore);
            d = d > 0 ? d : maxAbsDeltaScore;
            startTemperature = (-1.0 * d) / Math.log(startRate);
        } else if (useMax) {
            startTemperature = (-1.0 * maxAbsDeltaScore) / Math.log(startRate);
        } else {
            startTemperature = (-1.0 * minAbsDeltaScore) / Math.log(startRate);
        }
    }

    public void updateEndTemperature() {
        endTemperature = (-1.0 * minAbsDeltaScore) / Math.log(endRate);
    }

    public void updateTemperature() {
        updateStartTemperature();
        updateEndTemperature();
        if (useExp) {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double startX = Math.log(startY);
            double endX = Math.log(endY);
            double xStartToEnd = interpolate(startX, endX, time0to1);
            double temperature = Math.exp(xStartToEnd);

            inverseTemperature = 1.0 / temperature;
        } else {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double temperature = interpolate(startY, endY, time0to1);

            inverseTemperature = 1.0 / temperature;
        }
    }

    public void updateRange() {
    }

    public void updateTime() {
        time = useTime ? Main.watch.getSecond() : numIterations;
    }

    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 boolean isTLE() {
        return time >= endTime;
    }

    public boolean accept(double deltaScore) {
        double abs = Math.abs(deltaScore);
        if (abs > 1e-9) {
            helper.add(deltaScore);
            minAbsDeltaScore = Math.min(minAbsDeltaScore, abs);
            maxAbsDeltaScore = Math.max(maxAbsDeltaScore, abs);
        }
        return acceptS(deltaScore);
    }

    public boolean acceptB(double deltaScore) {
        validIterations++;
        if (deltaScore > -1e-9) {
            acceptIterations++;
            lastAcceptIterations = numIterations;
            return true;
        }

        assert deltaScore < 0;
        assert 1.0 / inverseTemperature >= 0;

        if (deltaScore * inverseTemperature < -10) {
            return false;
        }

        if (Main.rng.nextDouble() < Math.exp(deltaScore * inverseTemperature)) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            lastAcceptIterations = numIterations;
            return true;
        }
        return false;
    }

    public boolean acceptS(double deltaScore) {
        validIterations++;
        if (deltaScore < 1e-9) {
            acceptIterations++;
            lastAcceptIterations = numIterations;
            return true;
        }
        if (-deltaScore * inverseTemperature < -10) {
            return false;
        }
        if (Main.rng.nextDouble() < Math.exp(-deltaScore * inverseTemperature)) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            lastAcceptIterations = numIterations;
            return true;
        }
        return false;
    }

}

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 UnionFind {
    private int[] par;
    private int[] rank;

    public UnionFind(int capacity) {
        par = new int[capacity];
        rank = new int[capacity];
    }

    public void init(int n) {
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    public int getRoot(int x) {
        if (par[x] == x) {
            return x;
        } else {
            par[x] = getRoot(par[x]);
            return par[x];
        }
    }

    public void unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y) {
            return;
        }
        if (rank[x] < rank[y]) {
            par[x] = y;
        } else {
            par[y] = x;
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
    }

    public boolean isSame(int x, int y) {
        return getRoot(x) == getRoot(y);
    }
}

class Pair<T extends Comparable<T>, S> implements Comparable<Pair<T, S>> {
    public T first;
    public S second;

    public Pair(T t, S s) {
        this.first = t;
        this.second = s;
    }

    private int hash = 0;

    @Override
    public int hashCode() {
        if (hash == 0) {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((first == null) ? 0 : first.hashCode());
            result = prime * result + ((second == null) ? 0 : second.hashCode());
            hash = result;
        }
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Pair<T, S> other = (Pair<T, S>) obj;
        if (first == null) {
            if (other.first != null)
                return false;
        } else if (!first.equals(other.first))
            return false;
        if (second == null) {
            if (other.second != null)
                return false;
        } else if (!second.equals(other.second))
            return false;
        return true;
    }

    @Override
    public int compareTo(Pair<T, S> o) {
        return first.compareTo(o.first);
    }
}

class IntQueue {
    private int[] queue;
    private int current;
    private int size;

    public IntQueue(int capacity) {
        queue = new int[capacity];
    }

    public void clear() {
        init();
    }

    public void init() {
        current = 0;
        size = 0;
    }

    public boolean isEmpty() {
        return current == size;
    }

    public int poll() {
        return queue[current++];
    }

    public void add(int value) {
        queue[size++] = value;
    }
}

class IntSet {
    private static final int EMPTY = -1;
    private int size;
    private int[] indexToValue;
    private int[] valueToIndex;

    public IntSet(int capacity) {
        this.size = 0;
        indexToValue = new int[capacity];
        valueToIndex = new int[capacity];
        Arrays.fill(valueToIndex, EMPTY);
    }

    public boolean add(int value) {
        if (valueToIndex[value] != EMPTY) {
            return false;
        }
        indexToValue[size] = value;
        valueToIndex[indexToValue[size]] = size;
        size++;
        return true;
    }

    public boolean remove(int index) {
        if (size == 0) {
            return false;
        }
        assert index < size;
        int swap = indexToValue[index];
        indexToValue[index] = indexToValue[size - 1];
        indexToValue[size - 1] = swap;

        valueToIndex[indexToValue[index]] = index;
        valueToIndex[indexToValue[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 int get(int index) {
        assert index < size;
        return indexToValue[index];
    }

    public int indexOf(int value) {
        return valueToIndex[value];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() <= 0;
    }

    public void clear() {
        for (; size() > 0;) {
            remove(0);
        }
    }

    public boolean contains(int value) {
        return indexOf(value) != EMPTY;
    }

}

class TextFileIO {
    public static String read0(File file, String encoding) {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            char[] ch = new char[50000];
            int read;
            while ((read = reader.read(ch)) > 0) {
                String s = new String(ch, 0, read);
                sb.append(s);
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return sb.toString();
    }

    public static String read(File file) {
        return read(file, "UTF-8");
    }

    public static String read(File file, String encoding) {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            for (String line; (line = reader.readLine()) != null;) {
                sb.append(line + "\n");
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return sb.toString();
    }

    public static String[] read2(File file, String encoding) {
        ArrayList<String> list = new ArrayList<String>();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            for (String line; (line = reader.readLine()) != null;) {
                list.add(line);
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return (String[]) list.toArray(new String[list.size()]);
    }

    public static ArrayList<String> readLines(File file) {
        return read3(file, "UTF-8");
    }

    public static ArrayList<String> readLines(File file, String encoding) {
        return read3(file, encoding);
    }

    public static ArrayList<String> read3(File file) {
        return read3(file, "UTF-8");
    }

    public static ArrayList<String> read3(File file, String encoding) {
        ArrayList<String> res = new ArrayList<String>();

        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
            for (String line; (line = reader.readLine()) != null;) {
                res.add(line);
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return res;
    }

    public static List<String> readLines(Path file, Charset encoding) {
        try (BufferedReader reader = Files.newBufferedReader(file, encoding)) {
            return reader.lines().collect(Collectors.toList());
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        ArrayList<String> res = new ArrayList<String>();
        return res;
    }

    public static ArrayList<String> readFirstNLines(int numLines, File file) {
        return readFirstNLines(numLines, file, "UTF-8");
    }

    public static ArrayList<String> readFirstNLines(int numLines, File file, String encoding) {
        ArrayList<String> res = new ArrayList<String>();
        BufferedReader reader = null;
        try {
            reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding));
            for (String line; (line = reader.readLine()) != null;) {
                res.add(line);
                if (res.size() >= numLines) {
                    break;
                }
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (reader != null) {
                try {
                    reader.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
        return res;
    }

    private static void mkParents(File file) {
        File parentFile = file.getParentFile();
        if (!parentFile.exists()) {
            for (int i = 0; i < 5; i++) {
                if (parentFile.mkdirs()) {
                    break;
                }
            }
        }
    }

    public static void write(String contents, File file, String encoding) {
        mkParents(file);

        BufferedWriter writer = null;
        try {
            writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file), encoding));
            writer.write(contents);
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (writer != null) {
                try {
                    writer.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public static void write(String contents, Path file, Charset encoding) {
        try {
            Files.createDirectories(file.getParent());
        } catch (IOException e) {
            e.printStackTrace();
        }
        try (BufferedWriter writer = Files.newBufferedWriter(file, encoding)) {
            writer.write(contents);
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static void write(String contents, Path file) {
        write(contents, file, StandardCharsets.UTF_8);
    }

    public static void append(String contents, File file, String encoding) {
        mkParents(file);

        BufferedWriter writer = null;
        try {
            writer = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file, true), encoding));
            writer.append(contents);
            writer.flush();
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (writer != null) {
                try {
                    writer.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public static void appendln(String contents, File file, String encoding) {
        append(contents + "\n", file, encoding);
    }

    public static void write(String contents) {
        write(contents, new File("./debug.txt"), "UTF-8");
    }

    public static void write(String contents, File file) {
        write(contents, file, "UTF-8");
    }

    public static void writeln(String contents) {
        write(contents + "\n", new File("./debug.txt"), "UTF-8");
    }

    public static void writeln(String contents, File file) {
        write(contents + "\n", file, "UTF-8");
    }

    public static void append(String contents) {
        append(contents, new File("./debug.txt"), "UTF-8");
    }

    public static void append(String contents, File file) {
        append(contents, file, "UTF-8");
    }

    public static void appendln(String contents) {
        append(contents + "\n", new File("./debug.txt"), "UTF-8");
    }

    public static void appendln(String contents, File file) {
        append(contents + "\n", file, "UTF-8");
    }

    public static String read() {
        return read(new File("./debug.txt"), "UTF-8");
    }

    public static int calculateNumLines(File file) {
        return calculateNumLines(file, "UTF-8");
    }

    public static int calculateNumLines(File file, String encoding) {
        int numLines = 0;
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
            for (String line; (line = reader.readLine()) != null;) {
                numLines++;
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return numLines;
    }

    public static void printRandomLines(double d, File file) {
        printRandomLines(d, file, "UTF-8");
    }

    public static void printRandomLines(double d, File file, String encoding) {
        Random rng = new Random(System.nanoTime());
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), encoding))) {
            for (String line; (line = reader.readLine()) != null;) {
                if (rng.nextDouble() < d) {
                    Utils.debug(line);
                }
            }
        } catch (UnsupportedEncodingException e) {
            e.printStackTrace();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

}

class MeanHelper {
    private double max;
    private double min;
    private double sum;
    private double sumSquared;
    private double sumCubed;
    private double sumFourth;
    private int count;

    public MeanHelper() {
        clear();
    }

    public void add(double value) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value;
        double valueSquared = value * value;
        sumSquared += valueSquared;
        sumCubed += valueSquared * value;
        sumFourth += valueSquared * valueSquared;
        count++;
    }

    public void add(double value, double number) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value * number;
        double valueSquared = value * value;
        sumSquared += valueSquared * number;
        sumCubed += valueSquared * value * number;
        sumFourth += valueSquared * valueSquared * number;
        count += number;
    }

    public double kurtosis(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumFourth - 4.0 * mu * sumCubed + 6.0 * mu * mu * sumSquared - 3.0 * mu * mu * mu * sum) / count / (sigma * sigma * sigma * sigma);
    }

    public double skewness(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumCubed - 3.0 * mu * sumSquared + 2.0 * mu * mu * sum) / count / (sigma * sigma * sigma);
    }

    public double mean() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sum / count;
    }

    public double mean(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sum / count;
    }

    public double sumOfSquaredError() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sumSquared - sum * sum / count;
    }

    public double sumOfSquaredError(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sumSquared - sum * sum / count;
    }

    public double variance() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double variance(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double unbiasedVariance() {
        if (count - 1 == 0) {
            throw new AssertionError();
        }
        return (count * variance()) / (count - 1);
    }

    private double unbiasedVariance(double defaultValue) {
        if (count - 1 == 0) {
            return defaultValue;
        }
        return (count * variance()) / (count - 1);
    }

    public double standardDeviation() {
        return Math.sqrt(variance());
    }

    public double standardDeviation(double defaultValue) {
        return Math.sqrt(variance(defaultValue));
    }

    public double unbiasedStandardDeviation() {
        return Math.sqrt(unbiasedVariance());
    }

    public double unbiasedStandardDeviation(double defaultValue) {
        return Math.sqrt(unbiasedVariance(defaultValue));
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public void clear() {
        max = Double.NEGATIVE_INFINITY;
        min = Double.POSITIVE_INFINITY;
        sum = 0;
        sumSquared = 0;
        sumCubed = 0;
        sumFourth = 0;
        count = 0;
    }

    public double max() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return max;
    }

    public double max(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return max;
    }

    public double min() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return min;
    }

    public double min(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return min;
    }

    public int count() {
        return count;
    }

    public double sum() {
        return sum;
    }

    public double sumSquared() {
        return sumSquared;
    }
}

class Graph implements IGraph {
    private ArrayList<IntSet2> graph;
    private int numNodes;

    public Graph(int numNodes) {
        this.numNodes = numNodes;

        graph = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            graph.add(new IntSet2());
        }
    }

    @Override
    public int numNodes() {
        return numNodes;
    }

    @Override
    public void addEdge(int node, int node2) {
        graph.get(node).add(node2);
        graph.get(node2).add(node);
    }

    @Override
    public void removeEdge(int node, int node2) {
        graph.get(node).removeValue(node2);
        graph.get(node2).removeValue(node);
    }

    @Override
    public void clearEdges() {
        for (int node = 0; node < numNodes; node++) {
            graph.get(node).clear();
        }
    }

    @Override
    public void copy(IGraph g) {
        clearEdges();
        for (int node = 0; node < g.numNodes(); node++) {
            for (int i = 0; i < g.degree(node); i++) {
                int vertex = g.getNode(node, i);
                graph.get(node).add(vertex);
            }
        }
    }

    @Override
    public int getNode(int node, int index) {
        return graph.get(node).get(index);
    }

    @Override
    public int degree(int node) {
        return graph.get(node).size();
    }

    @Override
    public boolean hasEdge(int node, int node2) {
        return graph.get(node).contains(node2);
    }

}

interface IGraph {

    void addEdge(int node, int node2);

    void removeEdge(int node, int node2);

    boolean hasEdge(int node, int node2);

    void clearEdges();

    int getNode(int node, int index);

    int degree(int node);

    int numNodes();

    void copy(IGraph g);

}

final class Function {
    private Function() {
    }

    public static final double[] lower_bound_of_diam_aspl(int nnodes, int degree) {
        int diam = -1;
        double aspl = 0.0;
        int n = 1;
        int r = 1;
        while (true) {
            int tmp = n + degree * (int) Math.pow(degree - 1, r - 1);
            if (tmp >= nnodes) {
                break;
            }
            n = tmp;
            aspl += r * degree * Math.pow(degree - 1, r - 1);
            diam = r;
            r += 1;
        }
        diam += 1;
        aspl += diam * (nnodes - n);
        aspl /= (nnodes - 1);
        return new double[] { diam, aspl };
    }
}

class GifWriter {
    ImageWriter iw = ImageIO.getImageWritersByFormatName("gif").next();
    BufferedImage buffer;
    boolean finish = false;

    GifWriter(String filename) {
        File outfile = new File(filename);
        if (outfile.exists()) {
            Utils.debug("outfile.delete()", outfile.delete());
        }
        try {
            ImageOutputStream ios = ImageIO.createImageOutputStream(outfile);
            iw.setOutput(ios);
            iw.prepareWriteSequence(null);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    void add(BufferedImage buffer) {
        if (finish)
            return;
        try {
            iw.writeToSequence(new IIOImage(buffer, null, null), null);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    void close() {
        if (finish)
            return;
        try {
            finish = true;
            iw.endWriteSequence();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

class IntSet2 {
    private static final int EMPTY = -1;
    private ArrayList<Integer> indexToValue;
    private HashMap<Integer, Integer> 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);
        }

    }

}

class TimerManager {
    HashMap<String, Timer> map = new HashMap<>();

    public void start(String id) {
        if (map.get(id) == null) {
            map.put(id, new Timer());
        }
        Timer timer = map.get(id);
        timer.setDescription(id);
        timer.start();
    }

    public void stop(String id) {
        if (map.get(id) == null) {
            map.put(id, new Timer());
        }
        Timer timer = map.get(id);
        timer.setDescription(id);
        timer.stop();
    }

    public void print() {
        ArrayList<Timer> timers = new ArrayList<>();
        timers.addAll(map.values());
        Collections.sort(timers);
        for (int i = 0; i < timers.size(); i++) {
            timers.get(i).print();
        }
    }
}

class Timer implements Comparable<Timer> {
    private double time;
    private long start;
    private long stop;
    private int count;
    private String description;
    private boolean isRunning;

    public Timer() {
        reset();
    }

    @Override
    public int compareTo(Timer o) {
        if (time < o.time) {
            return 1;
        }
        if (time > o.time) {
            return -1;
        }
        return 0;
    }

    public int getCount() {
        return count;
    }

    public String getDescription() {
        return description;
    }

    public long getStart() {
        return start;
    }

    public long getStop() {
        return stop;
    }

    public double getTime() {
        return time;
    }

    public boolean isRunning() {
        return isRunning;
    }

    public void print() {
        if (count > 0) {
            Utils.debug(String.format("time, %10s, count, %10d, time/count, %12.9f, %s", TimeManager.toString(time), count, time / count, description));
        }
    }

    public void reset() {
        time = 0;
        start = 0;
        stop = 0;
        count = 0;
        isRunning = false;
    }

    public void setDescription(String description) {
        assert this.description == null || this.description.equals(description);
        if (this.description == null) {
            this.description = description;
        }
    }

    public void start() {
        assert isRunning == false;
        isRunning = true;
        start = System.nanoTime();
    }

    public void stop() {
        assert isRunning == true;
        stop = System.nanoTime();
        count++;
        time += (stop - start) * 1e-9;
        isRunning = false;
    }
}

class TimeManager {
    private long start;
    private int count;

    public TimeManager() {
        init();
    }

    public int getCount() {
        return count;
    }

    public double getSecond() {
        count++;
        return (System.nanoTime() - start) * 1e-9;
    }

    public long getTime() {
        count++;
        return System.nanoTime() - start;
    }

    public void init() {
        init(System.nanoTime());
    }

    public void init(long start) {
        this.start = start;
        count = 0;
    }

    public String toString() {
        return toString(getSecond());
    }

    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));
        }
    }

}

 



Approach TCO2015 MM R3 PegJumping と MM90 を合わせたような問題だった。MM90 では、私は人間でなかったので、 とりあえずその時の解き方からスタートした。そして、そのまま終わってしまった。

多スタート山登りを使いました。現在の状態からよさそうな状態を見つけるのに、ビームサーチを使いました。ビームサーチしても改善しなかったら、ベストスコアの解を途中まで進めてリスタートしました。

  • ビームサーチ
    • 深さ : 2*N
    • 幅 : 50
    • 評価 : スコアが良いほうが良い。同じスコアなら、ペグがターゲットに近いほうが良い。
    • ペグが到達してないターゲットを選んで、そのターゲットから1番近いペグを選んで、そのペグに近いペグを7個選んでビームサーチする。
    • 枝刈り : 7個のペグがすべてターゲットに到達したとき。
    • 枝刈り : 移動した数がベストスコアより多いとき。
    • 盤面重複の除去がすごく効きました。

盤面を分けてビームサーチしたり、たくさんジャンプできる盤面の評価を良くしたり、ペグがターゲットに到達したら次の状態の集合に加えるビームサーチとかいろいろ試したけど、MM90 の解より良くならなかった。ということで、きゅうりさんに言われたこれをみんなに言わないといけない。




source code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Random;

public class JumpAround {
    private static final int EMPTY = 1 << 20;
    private static final int WALL = 1 << 21;
    private static final int[] dr = { -1, 0, 0, 1, };
    private static final int[] dc = { 0, -1, 1, 0, };
    private static final char[] names = { 'U', 'L', 'R', 'D', };
    private int N;
    private int numPegs;
    private int[][] board;
    private int[][] boardTarget;
    private ArrayList pegs = new ArrayList<>();
    private ArrayList targets = new ArrayList<>();
    static final Watch watch = new Watch();
    static final XorShift rng = new XorShift(System.nanoTime());
    private SAState sa = new SAState();
    private int[][][] distanceFromTarget;
    private long[][] hashes;
    private long hash;
    private int maxMoves;
    private int countBeamsearch;
    private int bestScore = (int) 1e9;
    private String[] bestSolution = new String[0];

    private int[] bestPegIndexHistory;
    private boolean[] bestIsSlideHistory;
    private int[][] bestDirectionsHistory;
    private int bestMoves;

    private int[] saPegIndexHistory;
    private boolean[] saIsSlideHistory;
    private int[][] saDirectionsHistory;
    private int saMoves;

    public String[] findSolution(int N, int numPegs, char[] grid) {
        init(N, numPegs, grid);
        solve();
        return makeSolution();
    }

    private void init(int N, int numPegs, char[] grid) {
        this.N = N;
        this.numPegs = numPegs;
        Utils.debug("N", N, "numPegs", numPegs);
        maxMoves = N * numPegs;
        this.board = new int[N][N];
        this.boardTarget = new int[N][N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                char ch = grid[r * N + c];
                if (ch == '.') {
                    board[r][c] = EMPTY;
                    boardTarget[r][c] = EMPTY;
                }
                if (ch == '#') {
                    board[r][c] = WALL;
                    boardTarget[r][c] = WALL;
                }
                if (ch == 'X') {
                    board[r][c] = EMPTY;
                    boardTarget[r][c] = targets.size();
                    targets.add(new Point(r, c));
                }
                if (ch == 'P') {
                    board[r][c] = pegs.size();
                    boardTarget[r][c] = EMPTY;
                    pegs.add(new Point(r, c));
                }
            }
        }

        uncoveredTarget = numPegs;

        initDistanceFromTarget();
        initHash();

        used = new int[N][N];

        pegIndexHistory = new int[maxMoves];
        isSlideHistory = new boolean[maxMoves];
        directionsHistory = new int[maxMoves][];
        rHistory = new int[maxMoves];
        cHistory = new int[maxMoves];

        pegIndexInfo = new int[N * N];
        isSlideInfo = new boolean[N * N];
        directionsInfo = new int[N * N][];
        scoreInfo = new int[N * N];
        distanceInfo = new double[N * N];

        bestPegIndexHistory = new int[maxMoves];
        bestIsSlideHistory = new boolean[maxMoves];
        bestDirectionsHistory = new int[maxMoves][];

        saPegIndexHistory = new int[maxMoves];
        saIsSlideHistory = new boolean[maxMoves];
        saDirectionsHistory = new int[maxMoves][];
    }

    private void initDistanceFromTarget() {
        distanceFromTarget = new int[numPegs][N][N];

        for (int targetIndex = 0; targetIndex < numPegs; targetIndex++) {
            Point target = targets.get(targetIndex);
            for (int r = 0; r < N; r++) {
                Arrays.fill(distanceFromTarget[targetIndex][r], (int) 1e9);
            }

            LinkedList queue = new LinkedList<>();
            {
                Node e = new Node(target.r, target.c, 0);
                queue.add(e);
                distanceFromTarget[targetIndex][target.r][target.c] = 0;
            }
            for (; !queue.isEmpty();) {
                Node currentNode = queue.poll();

                for (int direction = 0; direction < dr.length; direction++) {
                    int nr = currentNode.r + dr[direction];
                    int nc = currentNode.c + dc[direction];
                    if (!isValid(nr) || !isValid(nc)) {
                        continue;
                    }
                    if (boardTarget[nr][nc] == WALL) {
                        continue;
                    }
                    int nextDistance = currentNode.distance + 1;
                    if (nextDistance < distanceFromTarget[targetIndex][nr][nc]) {
                        Node e = new Node(nr, nc, nextDistance);
                        queue.add(e);
                        distanceFromTarget[targetIndex][nr][nc] = nextDistance;
                    }
                }
                {
                    for (int direction = 0; direction < dr.length; direction++) {
                        int nr = currentNode.r + dr[direction];
                        int nc = currentNode.c + dc[direction];
                        if (!isValid(nr) || !isValid(nc)) {
                            continue;
                        }
                        if (boardTarget[nr][nc] != WALL) {
                            continue;
                        }
                        int nr2 = currentNode.r + 2 * dr[direction];
                        int nc2 = currentNode.c + 2 * dc[direction];
                        if (!isValid(nr2) || !isValid(nc2)) {
                            continue;
                        }
                        if (boardTarget[nr2][nc2] == WALL) {
                            continue;
                        }
                        int nextDistance = currentNode.distance + (currentNode.jump ? 0 : 1);
                        if (nextDistance < distanceFromTarget[targetIndex][nr2][nc2]) {
                            Node e = new Node(nr2, nc2, nextDistance, true);
                            queue.addFirst(e);
                            distanceFromTarget[targetIndex][nr2][nc2] = nextDistance;
                        }
                    }
                }
            }
        }
    }

    private int[][] searchDistance(int pegIndex) {
        int[][] distance = new int[N][N];
        for (int r = 0; r < N; r++) {
            Arrays.fill(distance[r], (int) 1e9);
        }

        Point peg = pegs.get(pegIndex);

        LinkedList queue = new LinkedList<>();
        {
            Node e = new Node(peg.r, peg.c, 0);
            queue.add(e);
            distance[peg.r][peg.c] = 0;
        }
        for (; !queue.isEmpty();) {
            Node currentNode = queue.poll();

            for (int direction = 0; direction < dr.length; direction++) {
                int nr = currentNode.r + dr[direction];
                int nc = currentNode.c + dc[direction];
                if (!isValid(nr) || !isValid(nc)) {
                    continue;
                }
                if (board[nr][nc] == WALL) {
                    continue;
                }
                int nextDistance = currentNode.distance + 1;
                if (nextDistance < distance[nr][nc]) {
                    Node e = new Node(nr, nc, nextDistance);
                    queue.add(e);
                    distance[nr][nc] = nextDistance;
                }
            }
            {
                for (int direction = 0; direction < dr.length; direction++) {
                    int nr = currentNode.r + dr[direction];
                    int nc = currentNode.c + dc[direction];
                    if (!isValid(nr) || !isValid(nc)) {
                        continue;
                    }
                    if (board[nr][nc] == EMPTY) {
                        continue;
                    }
                    int nr2 = currentNode.r + 2 * dr[direction];
                    int nc2 = currentNode.c + 2 * dc[direction];
                    if (!isValid(nr2) || !isValid(nc2)) {
                        continue;
                    }
                    if (board[nr2][nc2] == WALL) {
                        continue;
                    }
                    int nextDistance = currentNode.distance + (currentNode.jump ? 0 : 1);
                    if (nextDistance < distance[nr2][nc2]) {
                        Node e = new Node(nr2, nc2, nextDistance, true);
                        queue.addFirst(e);
                        distance[nr2][nc2] = nextDistance;
                    }
                }
            }
        }
        return distance;
    }

    private void initHash() {
        hashes = new long[N][N];
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                hashes[r][c] = rng.nextLong();
            }
        }

        hash = 0;
    }

    private static final int[] numbers = new int[] { 7, };

    private void solve() {
        SA();
    }

    private void SA() {
        double second = Math.ceil(watch.getSecond());
        sa.init();
        for (;; ++sa.numIterations) {
            if ((sa.numIterations & ((1 << 1) - 1)) == 0) {
                sa.update();

                if (sa.isTLE()) {
                    Utils.debug(sa.numIterations, String.format("%.2f%%", 100.0 * sa.validIterations / sa.numIterations), String.format("%.2f%%", 100.0 * sa.acceptIterations / sa.validIterations), /* String.format("%4d", score), */ String.format("%4d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                    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("%4d", score), */ String.format("%4d", bestScore), String.format("%.6f", 1.0 / sa.inverseTemperature), String.format("%.6f", 1.0 / sa.lastAcceptTemperature));
                }

            }

            mutate();
        }
        Utils.debug("SA", "score", bestScore, "beam", countBeamsearch, "time", watch.getSecondString());
    }

    private int prevScore = (int) 1e9;

    private void mutate() {
        int currentScore = prevScore;
        for (;;) {
            if (uncoveredTarget == 0) {
                break;
            }
            if (watch.getSecond() > 9.5) {
                break;
            }
            int beforeUncoveredTargets = uncoveredTarget;

            ArrayList targetIndexes = new ArrayList<>();
            for (int targetIndex = 0; targetIndex < numPegs; targetIndex++) {
                if (withPeg(targetIndex)) {
                    continue;
                }
                targetIndexes.add(targetIndex);
            }
            int targetIndex = targetIndexes.get((int) (targetIndexes.size() * rng.nextDouble())).intValue();

            int usePegs = Math.min(numbers[0], numPegs);

            int nearestPegIndex = -1;
            {
                ArrayList> pairs = new ArrayList<>();
                for (int pegIndex = 0; pegIndex < numPegs; pegIndex++) {
                    if (withTarget(pegIndex)) {
                        continue;
                    }
                    Point peg = pegs.get(pegIndex);
                    pairs.add(new Pair(distanceFromTarget[targetIndex][peg.r][peg.c] + 1e-2 * rng.nextDouble(), pegIndex));
                }
                Collections.sort(pairs);
                nearestPegIndex = pairs.get(0).second.intValue();
            }

            ArrayList pegIndexes = new ArrayList<>();
            {
                int[][] distanceFromPeg = searchDistance(nearestPegIndex);
                ArrayList> pairs = new ArrayList<>();
                for (int pegIndex = 0; pegIndex < numPegs; pegIndex++) {
                    Point peg = pegs.get(pegIndex);
                    pairs.add(new Pair(distanceFromPeg[peg.r][peg.c] + 1e-2 * rng.nextDouble(), pegIndex));
                }
                Collections.sort(pairs);
                for (int i = 0; i < usePegs; i++) {
                    pegIndexes.add(pairs.get(i).second);
                }
            }

            int maxDepth = 2 * N;
            int maxWidth = 50;
            if (countBeamsearch == 0) {
                Utils.debug("maxWidth", maxWidth);
            }
            countBeamsearch++;
            ArrayList moves = beamsearch(pegIndexes, maxDepth, maxWidth, targetIndex);
            if (moves == null) {
                continue;
            }
            for (State state : moves) {
                assert (state.move.isSlide && canSlideMove(state.move.pegIndex, state.move.directions[0])) || (!state.move.isSlide && canJumpMove(state.move.pegIndex, state.move.directions[0]));
                next(state.move.pegIndex, state.move.isSlide, state.move.directions);
            }
            if (uncoveredTarget == beforeUncoveredTargets || uncoveredTarget == 0) {
                break;
            }
        }

        double deltaScore = score - currentScore;
        if (sa.accept(deltaScore)) {
            prevScore = score;

            saMoves = numMoves();
            for (int i = 0; i < numMoves(); i++) {
                saPegIndexHistory[i] = pegIndexHistory[i];
                saIsSlideHistory[i] = isSlideHistory[i];
                saDirectionsHistory[i] = directionsHistory[i];
            }

            saveBest();

            for (; numMoves() > 0;) {
                previous();
            }
            int useMoves = (int) (saMoves * rng.nextDouble());
            for (int i = 0; i < useMoves; i++) {
                next(saPegIndexHistory[i], saIsSlideHistory[i], saDirectionsHistory[i]);
            }
        } else {
            for (; numMoves() > 0;) {
                previous();
            }
            int useMoves = (int) (saMoves * rng.nextDouble());
            for (int i = 0; i < useMoves; i++) {
                next(saPegIndexHistory[i], saIsSlideHistory[i], saDirectionsHistory[i]);
            }
        }
    }

    private void saveBest() {
        if (score < bestScore && numMoves() < maxMoves) {
            bestScore = score;

            bestMoves = numMoves();
            for (int i = 0; i < numMoves(); i++) {
                bestPegIndexHistory[i] = pegIndexHistory[i];
                bestIsSlideHistory[i] = isSlideHistory[i];
                bestDirectionsHistory[i] = directionsHistory[i];
            }

        }
    }

    private void makeSolution2() {
        ArrayList solution = new ArrayList<>();
        for (; numMoves() > 0;) {
            previous();
        }
        for (int m = 0; m < bestMoves; m++) {
            Point peg = pegs.get(bestPegIndexHistory[m]);
            int r = peg.r;
            int c = peg.c;
            StringBuilder d = new StringBuilder();
            for (int i = 0; i < bestDirectionsHistory[m].length; i++) {
                d.append(names[bestDirectionsHistory[m][i]]);
            }
            solution.add(r + " " + c + " " + (bestIsSlideHistory[m] ? "S" : "J") + " " + d.toString());
            next(bestPegIndexHistory[m], bestIsSlideHistory[m], bestDirectionsHistory[m]);
        }
        bestSolution = (String[]) solution.toArray(new String[solution.size()]);
    }

    private HashSet usedHash = new HashSet<>();

    private ArrayList beamsearch(ArrayList pegIndexes, int maxDepth, int maxWidth, int targetIndex) {
        ArrayList currents = new ArrayList<>();
        ArrayList nexts = new ArrayList<>();
        State best = null;

        usedHash.clear();

        int currentNumMoves = numMoves();
        {
            int score = calculateScore();
            double distance = calculateSumDistance(pegIndexes, targetIndex);
            distance += 1e-2 * rng.nextDouble();
            State e = new State(null, null, score, distance);
            currents.add(e);
        }

        depthLoop: for (int depth = 0; depth < maxDepth; depth++) {
            if (currents.size() == 0) {
                break;
            }
            int beamWidth = Math.min(maxWidth, currents.size());
            CollectionsUtils.select(currents, 0, currents.size(), beamWidth);
            for (int width = 0; width < beamWidth; width++) {
                State currentState = currents.get(width);

                if (best == null || currentState.compareTo(best) < 0) {
                    best = currentState;
                }

                set(reverse2(toList(currentState)), currentNumMoves);
                if (numMoves() > bestScore) {
                    continue;
                }

                assert calculateScore() == currentState.score : Utils.toString("calculateScore()", calculateScore(), "currentState.score", currentState.score, "moveHistory.size()", numMoves(), "uncoveredTarget", uncoveredTarget, 2 * N, toList(currentState).size());
                if (withAllTarget(pegIndexes)) {
                    break depthLoop;
                }

                for (Integer p : pegIndexes) {
                    int pegIndex = p.intValue();
                    generateMoves(pegIndex, pegIndexes, targetIndex);
                    for (int info = 0; info < numInfos; info++) {
                        nexts.add(new State(currentState, new Move(pegIndexInfo[info], isSlideInfo[info], directionsInfo[info]), scoreInfo[info], distanceInfo[info]));
                    }
                }
            }
            {
                ArrayList swap = currents;
                currents = nexts;
                nexts = swap;
            }
            nexts.clear();
        }

        for (; numMoves() > currentNumMoves;) {
            previous();
        }

        if (best == null) {
            return null;
        }
        return reverse2(toList(best));
    }

    private boolean withAllTarget(ArrayList pegIndexes) {
        for (Integer p : pegIndexes) {
            if (!withTarget(p.intValue())) {
                return false;
            }
        }
        return true;
    }

    private double calculateSumDistance(ArrayList pegIndexes, int targetIndex) {
        double distance = 0;
        for (Integer pegIndex : pegIndexes) {
            Point peg = pegs.get(pegIndex.intValue());
            distance += distanceFromTarget[targetIndex][peg.r][peg.c];
        }
        return distance;
    }

    private int[] directions = new int[50 * 50 / 4];

    private int[] pegIndexInfo;
    private boolean[] isSlideInfo;
    private int[][] directionsInfo;
    private int[] scoreInfo;
    private double[] distanceInfo;
    private int numInfos;

    private int[][] used;
    private int numDfs;

    private void generateMoves(int pegIndex, ArrayList pegIndexes, int targetIndex) {
        numInfos = 0;
        for (int d = 0; d < dr.length; d++) {
            if (canSlideMove(pegIndex, d)) {
                next(pegIndex, true, new int[] { d });
                if (usedHash.add(hash)) {
                    pegIndexInfo[numInfos] = pegIndex;
                    isSlideInfo[numInfos] = true;
                    directionsInfo[numInfos] = new int[] { d };
                    scoreInfo[numInfos] = score;
                    distanceInfo[numInfos] = calculateSumDistance(pegIndexes, targetIndex);
                    numInfos++;
                }
                previous();
            }
        }

        {
            numDfs++;
            dfs(pegIndex, pegs.get(pegIndex).r, pegs.get(pegIndex).c, 0, pegIndexes, targetIndex, numMoves() + 1);
        }
    }

    private void dfs(int pegIndex, int r, int c, int jumpIndex, ArrayList pegIndexes, int targetIndex, int currentMoves) {
        if (used[r][c] == numDfs) {
            return;
        }
        used[r][c] = numDfs;
        for (int d = 0; d < dr.length; d++) {
            int nr = pegs.get(pegIndex).r + dr[d] + dr[d];
            int nc = pegs.get(pegIndex).c + dc[d] + dc[d];
            if (!isValid(nr) || !isValid(nc)) {
                continue;
            }
            if (used[nr][nc] == numDfs) {
                continue;
            }
            if (!canJumpMove(pegIndex, d)) {
                continue;
            }
            directions[jumpIndex] = d;
            boolean isSlide = false;
            next(pegIndex, isSlide, new int[] { d });
            if (usedHash.add(hash)) {
                int[] copyOf = Arrays.copyOf(directions, jumpIndex + 1);
                pegIndexInfo[numInfos] = pegIndex;
                isSlideInfo[numInfos] = isSlide;
                directionsInfo[numInfos] = copyOf;
                scoreInfo[numInfos] = score - numMoves() + currentMoves;
                distanceInfo[numInfos] = calculateSumDistance(pegIndexes, targetIndex);
                numInfos++;

                Point peg = pegs.get(pegIndex);
                dfs(pegIndex, peg.r, peg.c, jumpIndex + 1, pegIndexes, targetIndex, currentMoves);
            }
            previous();
        }
    }

    public static final void shuffle(int[] a, XorShift rng) {
        for (int i = a.length - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            swap(a, i, j);
        }
    }

    public static final void swap(int[] a, int i, int j) {
        int swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private void slideMove(int pegIndex, int direction) {
        int r = pegs.get(pegIndex).r;
        int c = pegs.get(pegIndex).c;
        int nr = r + dr[direction];
        int nc = c + dc[direction];
        assert isValid(nr) && isValid(nc);
        assert board[nr][nc] == EMPTY : Utils.toString(board[nr][nc], EMPTY);
        movePeg(board, r, c, nr, nc);
    }

    private void jumpMove(int pegIndex, int direction) {
        int r = pegs.get(pegIndex).r;
        int c = pegs.get(pegIndex).c;
        int nr = r + dr[direction];
        int nc = c + dc[direction];
        assert isValid(nr) && isValid(nc);
        assert board[nr][nc] != EMPTY;
        int nr2 = nr + dr[direction];
        int nc2 = nc + dc[direction];
        assert isValid(nr2) && isValid(nc2);
        assert board[nr2][nc2] == EMPTY;
        movePeg(board, r, c, nr2, nc2);
    }

    private void movePeg(int[][] board, int fromR, int fromC, int toR, int toC) {
        assert board[fromR][fromC] != EMPTY;
        assert board[toR][toC] == EMPTY;
        assert pegs.get(board[fromR][fromC]).r == fromR;
        assert pegs.get(board[fromR][fromC]).c == fromC;
        int swap = board[fromR][fromC];
        board[fromR][fromC] = board[toR][toC];
        board[toR][toC] = swap;
        pegs.get(board[toR][toC]).r = toR;
        pegs.get(board[toR][toC]).c = toC;
        assert board[fromR][fromC] == EMPTY;
        assert board[toR][toC] != EMPTY;
        assert pegs.get(board[toR][toC]).r == toR;
        assert pegs.get(board[toR][toC]).c == toC;
    }

    private boolean canSlideMove(int pegIndex, int direction) {
        int r = pegs.get(pegIndex).r;
        int c = pegs.get(pegIndex).c;
        int nr = r + dr[direction];
        int nc = c + dc[direction];
        if (!isValid(nr) || !isValid(nc)) {
            return false;
        }
        if (board[nr][nc] != EMPTY) {
            return false;
        }
        return true;
    }

    private boolean isValid(int v) {
        return v >= 0 && v < N;
    }

    private boolean canJumpMove(int pegIndex, int direction) {
        int r = pegs.get(pegIndex).r;
        int c = pegs.get(pegIndex).c;
        assert isValid(r) && isValid(c);
        assert board[r][c] != EMPTY;
        int nr = r + dr[direction];
        int nc = c + dc[direction];
        if (!isValid(nr) || !isValid(nc)) {
            return false;
        }
        if (board[nr][nc] == EMPTY) {
            return false;
        }
        int nr2 = nr + dr[direction];
        int nc2 = nc + dc[direction];
        if (!isValid(nr2) || !isValid(nc2)) {
            return false;
        }
        if (board[nr2][nc2] != EMPTY) {
            return false;
        }
        return true;
    }

    private int manhattanDistance(int r, int c, int r2, int c2) {
        return Math.abs(r - r2) + Math.abs(c - c2);
    }

    private boolean withPeg(int targetIndex) {
        Point targetPoint = targets.get(targetIndex);
        return board[targetPoint.r][targetPoint.c] != EMPTY;
    }

    private boolean withTarget(int pegIndex) {
        Point pegPoint = pegs.get(pegIndex);
        return boardTarget[pegPoint.r][pegPoint.c] != EMPTY;
    }

    public void set(ArrayList list, int startIndex) {
        int startIndexMinus1 = startIndex - 1;
        for (int i = 0; i < list.size() && startIndex + i < numMoves(); i++) {
            if (!isSameMove(startIndex + i, list.get(i))) {
                break;
            }
            startIndexMinus1 = startIndex + i;
        }
        for (; numMoves() > startIndexMinus1 + 1;) {
            previous();
        }
        for (int i = (startIndexMinus1 + 1) - (startIndex); i < list.size(); i++) {
            State state2 = list.get(i);
            next(state2.move.pegIndex, state2.move.isSlide, state2.move.directions);
        }
    }

    private boolean isSameMove(int numMoves, State state) {
        if (state.move.pegIndex != pegIndexHistory[numMoves]) {
            return false;
        }
        if (state.move.isSlide != isSlideHistory[numMoves]) {
            return false;
        }
        if (state.move.directions.length != directionsHistory[numMoves].length) {
            return false;
        }
        for (int i = 0; i < directionsHistory[numMoves].length; i++) {
            if (state.move.directions[i] != directionsHistory[numMoves][i]) {
                return false;
            }
        }
        return true;
    }

    private int uncoveredTarget;
    private int score;

    private int[] pegIndexHistory;
    private boolean[] isSlideHistory;
    private int[][] directionsHistory;
    private int[] rHistory;
    private int[] cHistory;
    private int numMoves;

    public void next(int pegIndex, boolean isSlide, int[] directions) {
        pegIndexHistory[numMoves] = pegIndex;
        isSlideHistory[numMoves] = isSlide;
        directionsHistory[numMoves] = directions;
        rHistory[numMoves] = pegs.get(pegIndex).r;
        cHistory[numMoves] = pegs.get(pegIndex).c;
        numMoves++;

        if (withTarget(pegIndex)) {
            uncoveredTarget++;
        }

        hash ^= hashes[pegs.get(pegIndex).r][pegs.get(pegIndex).c];

        if (isSlide) {
            slideMove(pegIndex, directions[0]);
        } else {
            for (int direction : directions) {
                jumpMove(pegIndex, direction);
            }
        }

        hash ^= hashes[pegs.get(pegIndex).r][pegs.get(pegIndex).c];

        if (withTarget(pegIndex)) {
            uncoveredTarget--;
        }

        score = calculateScore();
    }

    public void previous() {
        numMoves--;
        int pegIndex = pegIndexHistory[numMoves];
        int r = pegs.get(pegIndex).r;
        int c = pegs.get(pegIndex).c;

        if (withTarget(pegIndex)) {
            uncoveredTarget++;
        }

        hash ^= hashes[pegs.get(pegIndex).r][pegs.get(pegIndex).c];

        assert board[r][c] == pegIndex;
        assert pegs.get(pegIndex).r == r;
        assert pegs.get(pegIndex).c == c;
        movePeg(board, r, c, rHistory[numMoves], cHistory[numMoves]);
        assert board[rHistory[numMoves]][cHistory[numMoves]] == pegIndex;
        assert pegs.get(pegIndex).r == rHistory[numMoves];
        assert pegs.get(pegIndex).c == cHistory[numMoves];

        hash ^= hashes[pegs.get(pegIndex).r][pegs.get(pegIndex).c];

        if (withTarget(pegIndex)) {
            uncoveredTarget--;
        }

        score = calculateScore();
    }

    private ArrayList reverse2(ArrayList list) {
        for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
            list.set(r, list.set(l, list.get(r)));
        }
        return list;
    }

    private ArrayList toList(State state0) {
        ArrayList res = new ArrayList<>();
        for (State current = state0; current.parent != null; current = current.parent) {
            res.add(current);
        }
        return res;
    }

    private int calculateScore() {
        return numMoves() + uncoveredTarget * 2 * N;
    }

    private int numMoves() {
        return numMoves;
    }

    private String[] makeSolution() {
        makeSolution2();
        return bestSolution;
    }

    public static void main(String[] args) {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            int N = Integer.parseInt(br.readLine());
            int NumPegs = Integer.parseInt(br.readLine());
            char[] grid = new char[N * N];
            for (int i = 0; i < N * N; i++) {
                grid[i] = br.readLine().charAt(0);
            }

            JumpAround jp = new JumpAround();
            String[] ret = jp.findSolution(N, NumPegs, grid);

            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 Move {
    int pegIndex;
    boolean isSlide;
    int[] directions;

    public Move(int pegIndex, boolean isSlide, int[] directions) {
        this.pegIndex = pegIndex;
        this.isSlide = isSlide;
        this.directions = directions;
    }

    @Override
    public String toString() {
        return Utils.toString("pegIndex", pegIndex, "isSlide", isSlide, "directions", directions);
    }
}

class Point {
    int r;
    int c;

    public Point(int r, int c) {
        super();
        this.r = r;
        this.c = c;
    }

}

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 double nextDouble() {
        return (nextInt() >>> 1) * 4.6566128730773926E-10;
    }

    public int nextInt(int n) {
        return (int) (n * nextDouble());
    }

    public long nextLong() {
        long a = nextInt();
        long b = nextInt();
        return (a << 32) ^ b;
    }

}

class State implements Comparable {
    State parent;
    Move move;
    int score;
    double distance;

    public State(State parent, Move move, int score, double distance) {
        super();
        this.parent = parent;
        this.move = move;
        this.score = score;
        this.distance = distance;
    }

    @Override
    public int compareTo(State o) {
        if (score < o.score) {
            return -1;
        }
        if (score > o.score) {
            return 1;
        }
        if (distance < o.distance) {
            return -1;
        }
        if (distance > o.distance) {
            return 1;
        }
        return 0;
    }

    @Override
    public String toString() {
        return Utils.toString(move, "score", score, "distance", distance);
    }
}

class Pair, S> implements Comparable> {
    public T first;
    public S second;

    public Pair(T t, S s) {
        this.first = t;
        this.second = s;
    }

    private int hash = 0;

    @Override
    public int hashCode() {
        if (hash == 0) {
            final int prime = 31;
            int result = 1;
            result = prime * result + ((first == null) ? 0 : first.hashCode());
            result = prime * result + ((second == null) ? 0 : second.hashCode());
            hash = result;
        }
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Pair other = (Pair) obj;
        if (first == null) {
            if (other.first != null)
                return false;
        } else if (!first.equals(other.first))
            return false;
        if (second == null) {
            if (other.second != null)
                return false;
        } else if (!second.equals(other.second))
            return false;
        return true;
    }

    @Override
    public int compareTo(Pair o) {
        return first.compareTo(o.first);
    }
}

class CollectionsUtils {
    private CollectionsUtils() {
    }

    public static final  void shuffle(ArrayList list, Random rng) {
        for (int i = list.size() - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            CollectionsUtils.swap(list, i, j);
        }
    }

    public static final  void shuffle(ArrayList list, XorShift rng) {
        for (int i = list.size() - 1; i >= 0; i--) {
            int j = (int) ((i + 1) * rng.nextDouble());
            CollectionsUtils.swap(list, i, j);
        }
    }

    public static final  void select0(ArrayList a, int l, int r, int k, Comparator comparator) {
        while (l < r) {
            int i = CollectionsUtils.partition3(a, l, r, comparator);
            if (i >= k)
                r = i - 1;
            if (i <= k)
                l = i + 1;
        }
    }

    public static final > void select(ArrayList a, int startInclusive, int endExclusive, int k, Comparator comparator) {
        select0(a, startInclusive, endExclusive - 1, k, comparator);
    }

    public static final > void select0(ArrayList a, int l, int r, int k) {
        while (l < r) {
            int i = CollectionsUtils.partition3(a, l, r);
            if (i >= k)
                r = i - 1;
            if (i <= k)
                l = i + 1;
        }
    }

    public static final > void select(ArrayList a, int startInclusive, int endExclusive, int k) {
        select0(a, startInclusive, endExclusive - 1, k);
    }

    public static final  void swap(ArrayList a, int i, int j) {
        T swap = a.set(i, a.get(j));
        a.set(j, swap);
    }

    public static final  void sort3(ArrayList a, int i, int j, int k, Comparator comparator) {
        if (comparator.compare(a.get(i), a.get(j)) > 0) {
            swap(a, i, j);
        }
        if (comparator.compare(a.get(i), a.get(k)) > 0) {
            swap(a, i, k);
        }
        if (comparator.compare(a.get(j), a.get(k)) > 0) {
            swap(a, j, k);
        }
    }

    public static final > void sort3(ArrayList a, int i, int j, int k) {
        if (a.get(i).compareTo(a.get(j)) > 0) {
            swap(a, i, j);
        }
        if (a.get(i).compareTo(a.get(k)) > 0) {
            swap(a, i, k);
        }
        if (a.get(j).compareTo(a.get(k)) > 0) {
            swap(a, j, k);
        }
    }

    public static final  int partition3(ArrayList a, int l, int r, Comparator comparator) {
        int center = (l + r) >>> 1;
        sort3(a, l, center, r, comparator);
        swap(a, center, r - 1);
        if (r - l < 3) {
            return l;
        }
        int r1 = r - 1;
        T v = a.get(r1);
        int i = l - 1;
        int j = r1;
        for (;;) {
            for (; comparator.compare(a.get(++i), v) < 0;) {
            }
            for (; comparator.compare(a.get(--j), v) > 0;) {
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, r1);
        return i;
    }

    public static final > int partition3(ArrayList a, int l, int r) {
        int center = (l + r) >>> 1;
        sort3(a, l, center, r);
        swap(a, center, r - 1);
        if (r - l < 3) {
            return l;
        }
        int r1 = r - 1;
        T v = a.get(r1);
        int i = l - 1;
        int j = r1;
        for (;;) {
            for (; a.get(++i).compareTo(v) < 0;) {
            }
            for (; a.get(--j).compareTo(v) > 0;) {
            }
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, r1);
        return i;
    }

    public static final > int partition(ArrayList a, int l, int r) {
        int i = l - 1, j = r;
        T v = a.get(r);
        for (;;) {
            while (a.get(++i).compareTo(v) < 0)
                ;
            while (v.compareTo(a.get(--j)) < 0)
                if (j == l)
                    break;
            if (i >= j)
                break;
            swap(a, i, j);
        }
        swap(a, i, r);
        return i;
    }

    public static final  void sort(ArrayList a, int lInclusive, int rInclusive, Comparator comparator) {
        if (lInclusive >= rInclusive) {
            return;
        }
        int k = partition3(a, lInclusive, rInclusive, comparator);
        sort(a, lInclusive, k - 1, comparator);
        sort(a, k + 1, rInclusive, comparator);
    }

    public  ArrayList reverse(ArrayList list) {
        for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
            list.set(r, list.set(l, list.get(r)));
        }
        return list;
    }

    public  ArrayList newReverse(ArrayList list) {
        ArrayList res = new ArrayList<>();
        for (int i = list.size() - 1; i >= 0; i--) {
            res.add(list.get(i));
        }
        return res;
    }

}

class SAState {

    public static final boolean useTime = true;

    public double startTime = 0;
    public double endTime = 9.5;
    public double time = startTime;
    public double startTemperature = 0;
    public double endTemperature = 0;
    public double inverseTemperature = 1.0 / startTemperature;
    public double lastAcceptTemperature = startTemperature;

    public double startRange = 0;
    public double endRange = 0;
    public double range = startRange;

    public int numIterations;
    public int validIterations;
    public int acceptIterations;

    private double minAbsDeltaScore;
    private double maxAbsDeltaScore;
    private MeanHelper helper = new MeanHelper();

    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;

        minAbsDeltaScore = 1e99;
        maxAbsDeltaScore = 1e-99;
        helper.clear();

        startTime = useTime ? JumpAround.watch.getSecond() : numIterations;

        update();
        lastAcceptTemperature = inverseTemperature;
    }

    public void update() {
        updateTime();
        updateTemperature();
        updateRange();
    }

    public boolean useMean = true;
    public boolean useMax = !true;
    public double startRate = 0.01;
    public double endRate = 0.01;
    public boolean useExp = !true;

    public void updateStartTemperature() {
        if (useMean) {
            double d = helper.mean(maxAbsDeltaScore);
            d = d > 0 ? d : maxAbsDeltaScore;
            startTemperature = (-1.0 * d) / Math.log(startRate);
        } else if (useMax) {
            startTemperature = (-1.0 * maxAbsDeltaScore) / Math.log(startRate);
        } else {
            startTemperature = (-1.0 * minAbsDeltaScore) / Math.log(startRate);
        }
    }

    public void updateEndTemperature() {
        endTemperature = (-1.0 * minAbsDeltaScore) / Math.log(endRate);
    }

    public void updateTemperature() {
        if (useExp) {
            double time0to1 = elapsedPercentage(startTime, endTime, time);
            double startY = startTemperature;
            double endY = endTemperature;
            double startX = Math.log(startY);
            double endX = Math.log(endY);
            double xStartToEnd = interpolate(startX, endX, time0to1);
            double temperature = Math.exp(xStartToEnd);

            inverseTemperature = 1.0 / temperature;
        } else {
            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 ? JumpAround.watch.getSecond() : numIterations;
    }

    public boolean isTLE() {
        return time >= endTime;
    }

    public boolean accept(double deltaScore) {
        double abs = Math.abs(deltaScore);
        if (abs > 1e-9) {
            helper.add(deltaScore);
            minAbsDeltaScore = Math.min(minAbsDeltaScore, abs);
            maxAbsDeltaScore = Math.max(maxAbsDeltaScore, abs);
        }
        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;

        if (deltaScore * inverseTemperature < -10) {
            return false;
        }
        if (log[JumpAround.rng.nextInt() & 32767] < deltaScore * inverseTemperature) {
            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;

        if (-deltaScore * inverseTemperature < -10) {
            return false;
        }
        if (log[JumpAround.rng.nextInt() & 32767] < deltaScore * inverseTemperature) {
            acceptIterations++;
            lastAcceptTemperature = inverseTemperature;
            return true;
        }
        return false;
    }

}

class MeanHelper {
    private double max;
    private double min;
    private double sum;
    private double sumSquared;
    private double sumCubed;
    private double sumFourth;
    private int count;

    public MeanHelper() {
        clear();
    }

    public void add(double value) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value;
        double valueSquared = value * value;
        sumSquared += valueSquared;
        sumCubed += valueSquared * value;
        sumFourth += valueSquared * valueSquared;
        count++;
    }

    public void add(double value, double number) {
        max = Math.max(max, value);
        min = Math.min(min, value);
        sum += value * number;
        double valueSquared = value * value;
        sumSquared += valueSquared * number;
        sumCubed += valueSquared * value * number;
        sumFourth += valueSquared * valueSquared * number;
        count += number;
    }

    public double kurtosis(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumFourth - 4.0 * mu * sumCubed + 6.0 * mu * mu * sumSquared - 3.0 * mu * mu * mu * sum) / count / (sigma * sigma * sigma * sigma);
    }

    public double skewness(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double sigma = standardDeviation(0);
        if (sigma == 0) {
            return 0;
        }
        double mu = mean(0);
        return (sumCubed - 3.0 * mu * sumSquared + 2.0 * mu * mu * sum) / count / (sigma * sigma * sigma);
    }

    public double mean() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sum / count;
    }

    public double mean(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sum / count;
    }

    public double sumOfSquaredError() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return sumSquared - sum * sum / count;
    }

    public double sumOfSquaredError(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return sumSquared - sum * sum / count;
    }

    public double variance() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double variance(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        double E_XX = sumSquared / count;
        double E_X = sum / count;
        return E_XX - E_X * E_X;
    }

    public double unbiasedVariance() {
        if (count - 1 == 0) {
            throw new AssertionError();
        }
        return (count * variance()) / (count - 1);
    }

    private double unbiasedVariance(double defaultValue) {
        if (count - 1 == 0) {
            return defaultValue;
        }
        return (count * variance()) / (count - 1);
    }

    public double standardDeviation() {
        return Math.sqrt(variance());
    }

    public double standardDeviation(double defaultValue) {
        return Math.sqrt(variance(defaultValue));
    }

    public double unbiasedStandardDeviation() {
        return Math.sqrt(unbiasedVariance());
    }

    public double unbiasedStandardDeviation(double defaultValue) {
        return Math.sqrt(unbiasedVariance(defaultValue));
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public void clear() {
        max = Double.NEGATIVE_INFINITY;
        min = Double.POSITIVE_INFINITY;
        sum = 0;
        sumSquared = 0;
        sumCubed = 0;
        sumFourth = 0;
        count = 0;
    }

    public double max() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return max;
    }

    public double max(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return max;
    }

    public double min() {
        if (isEmpty()) {
            throw new AssertionError();
        }
        return min;
    }

    public double min(double defaultValue) {
        if (isEmpty()) {
            return defaultValue;
        }
        return min;
    }

    public int count() {
        return count;
    }

    public double sum() {
        return sum;
    }

    public double sumSquared() {
        return sumSquared;
    }
}

class Node {
    int r;
    int c;
    int distance;
    boolean jump;

    public Node(int r, int c, int distance) {
        super();
        this.r = r;
        this.c = c;
        this.distance = distance;
        this.jump = false;
    }

    public Node(int r, int c, int distance, boolean jump) {
        super();
        this.r = r;
        this.c = c;
        this.distance = distance;
        this.jump = jump;
    }
}

 

このページのトップヘ