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