algorithm - 如何解决达到矩阵问题结束所需的最少步骤？

Question

给定一个包含每个元素初始状态的矩阵，找到从左上角到右下角到达的最少步数？

条件:

任何元素的初始状态将随机为北、东、南或西之一。在每一步，我们要么不移动任何地方，要么沿着该元素当前状态的方向移动(当然我们永远不会离开矩阵)任何一步都会同时改变矩阵所有元素的状态。状态以顺时针循环方式变化，即从 N -> E -> S -> W。即使我们一步不移动，状态也会发生变化

Answer 1

一个重要的观察是矩阵有 4 个不同的“版本”:每 4 个步骤的倍数，矩阵的内容将完全相同。

您可以将这 4 个矩阵想象成三维(Z 方向)，其中 Z 可以是 0、1、2 或 3。将其想象成一个 3D 阵列，其中 4 x 2D 阵列彼此分层。

有了那个 3D 矩阵，“旋转”值的魔力就消失了:这 4 个矩阵中的每一个现在都是静态的。

现在的一个步骤是:

• 按照当前单元格内容指示的方向移动，因此 X 或 Y 发生变化，或者
• X 和 Y 保持不变的移动

...但在这两种情况下 Z 都变成 (Z+1)%4

目标单元格现在实际上是一组 4 个单元格，因为在您到达右下角时 Z 是什么并不重要。

如果构建此(未加权、有向)图，则可以实现简单的 BFS 搜索。问题解决了。

实现

我想我会为以下示例输入矩阵制作一个小动画:

[
    [2, 0, 0, 2, 1, 0, 3],
    [0, 0, 0, 2, 0, 0, 1],
    [3, 2, 0, 3, 3, 3, 0],
]

数字代表当前可能的方向:0 = 北，1 = 东，2 = 南，3 = 西。

该算法由两个函数组成。一个是 Node 类的方法 shortestPathTo，它实现了从一个节点到一组目标节点的通用 BFS 搜索。第二个函数 createGraph 会将输入矩阵转换为如上所述的图形。创建此图后，可以在左上角的节点上调用 shortestPathTo 方法。它返回一个 path，一个要访问的节点数组。

该路径用于制作动画，这是代码的下半部分处理的内容。该部分与算法关系不大，可以忽略。

class Node { // Generic Node class; not dependent on specific problem
    constructor(value, label) {
        this.value = value;
        this.label = label;
        this.neighbors = [];
    }
    addEdgeTo(neighbor) {
        this.neighbors.push(neighbor);
    }
    shortestPathTo(targets) {
        targets = new Set(targets); // convert Array to Set
        // Standard BFS
        let queue = [this]; // Start at current node
        let comingFrom = new Map;
        comingFrom.set(this, null);
        while (queue.length) {
            let node = queue.shift();
            if (targets.has(node)) { // Found!
                let path = []; // Build path from back-linked list
                while (node) {
                    path.push(node);
                    node = comingFrom.get(node);
                }
                return path.reverse();
            }
            for (let nextNode of node.neighbors) {
                if (!comingFrom.has(nextNode)) {
                    comingFrom.set(nextNode, node);
                    queue.push(nextNode);
                }
            }
        }
        return []; // Could not reach target node
    }
}

function createGraph(matrix) {
    // Convert the matrix and its move-rules into a directed graph
    const numCols = matrix[0].length;
    const numRows = matrix.length;
    const numNodes = numRows * numCols * 4; // |Y| * |X| * |Z|
    // Create the nodes
    const nodes = [];
    for (let y = 0; y < numRows; y++) 
        for (let x = 0; x < numCols; x++) 
            for (let z = 0; z < 4; z++) {
                let dir = (matrix[y][x] + z) % 4;
                nodes.push(new Node({x, y, z, dir}, "<" + x + "," + y + ":" + "NESW"[dir] + ">"));
            }
    // Create the edges
    for (let i = 0; i < nodes.length; i++) {
        let node = nodes[i];
        let {x, y, z, dir} = node.value;
        // The "stand-still" neighbor:
        let j = i-z + (z+1)%4;
        node.addEdgeTo(nodes[j]);
        // The neighbor as determined by the node's "direction"
        let dj = 0;
        if      (dir == 0 && y   > 0      ) dj = -numCols*4;
        else if (dir == 1 && x+1 < numCols) dj = 4;
        else if (dir == 2 && y+1 < numRows) dj = numCols*4;
        else if (dir == 3 && x   > 0      ) dj = -4;
        if (dj) node.addEdgeTo(nodes[j+dj]);
    }
    // return the nodes of the graph
    return nodes;
}

// Sample matrix
let matrix = [
    [2, 0, 0, 2, 1, 0, 3],
    [0, 0, 0, 2, 0, 0, 1],
    [3, 2, 0, 3, 3, 3, 0],
];

// Calculate solution:
const nodes = createGraph(matrix);
const path = nodes[0].shortestPathTo(nodes.slice(-4));
// path now has the sequence of nodes to visit.

// I/O handling for this snippet
const size = 26;
const paint = () => new Promise(resolve => requestAnimationFrame(resolve));

function drawSquare(ctx, x, y, angle) {
    ctx.rect(x*size+0.5, y*size+0.5, size, size);
    ctx.stroke();
    ctx.beginPath();
    angle = (270 + angle) * Math.PI / 180;
    x = (x+0.5)*size;
    y = (y+0.5)*size;
    ctx.moveTo(x + 0.5, y + 0.5);
    ctx.lineTo(x + Math.cos(angle) * size * 0.4 + 0.5, y + Math.sin(angle) * size * 0.4 + 0.5);
    ctx.stroke();
}

function drawBall(ctx, x, y) {
    x = (x+0.5)*size;
    y = (y+0.5)*size;
    ctx.beginPath();
    ctx.arc(x, y, size * 0.2, 0, 2 * Math.PI);
    ctx.fillStyle = "red";
    ctx.fill();
}

async function draw(ctx, matrix, time=0, angle=0, curX=0, curY=0) {
    await paint();
    time = time % 4;
    ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.height);
    for (let y = 0; y < matrix.length; y++) {
        for (let x = 0; x < matrix[0].length; x++) {
            drawSquare(ctx, x, y, (matrix[y][x] + time) * 360 / 4 - angle);
        }
    }
    drawBall(ctx, curX, curY);
}

async function step(ctx, matrix, time, curX, curY, toX, toY) {
    for (let move = 100; move >= 0; move-=5) {
        await draw(ctx, matrix, time, 90, toX + (curX-toX)*move/100, toY + (curY-toY)*move/100);
    }
    for (let angle = 90; angle >= 0; angle-=5) {
        await draw(ctx, matrix, time, angle, toX, toY);
    }
}

async function animatePath(ctx, path) {
    for (let time = 1; time < path.length; time++) {    
        await step(ctx, matrix, time, path[time-1].value.x, path[time-1].value.y, path[time].value.x, path[time].value.y);
    }
}

const ctx = document.querySelector("canvas").getContext("2d");
draw(ctx, matrix);
document.querySelector("button").onclick = () => animatePath(ctx, path);

<button>Start</button><br>
<canvas width="400" height="160"></canvas>

您可以在代码中更改matrix的定义来尝试其他输入。