如何解决达到矩阵问题结束所需的最少步骤?
How to solve this minimum steps needed to reach end of matrix problem?
给定一个包含每个元素初始状态的矩阵,找到从左上角到右下角到达的最小步数?
条件:
任何元素的初始状态将随机为北、东、南或西之一。
在每一步,我们要么不移动任何地方,要么沿着该元素当前状态的方向移动(当然我们永远不会离开矩阵)
任何一步都会同时改变矩阵所有元素的状态。状态以顺时针循环方式变化,即从 N -> E -> S -> W。即使我们一步不移动,状态也会变化
一个重要的观察是矩阵有4个不同"versions":每4个步骤的倍数,矩阵的内容将完全相同。
您可以将这 4 个矩阵想象成三维 (Z-direction),其中 Z 可以是 0、1、2 或 3。将其想象成一个 3D 阵列,4 x 2D 阵列位于 each-other.
有了那个 3D 矩阵,"turning" 值的魔力消失了:这 4 个矩阵中的每一个现在都是静态的。
一个步骤现在是:
- 按照当前单元格内容指示的方向移动,因此 X 或 Y 发生变化,或者
- X 和 Y 保持不变的移动
...但在这两种情况下 Z 变为 (Z+1)%4
目标单元格现在实际上是一组 4 个单元格,因为到达 bottom-right 角时 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 = 西。
该算法由两个函数组成。一种是Nodeclass,shortestPathTo
的方法,它实现了从一个节点到一组目标节点的通用BFS搜索。第二个函数 createGraph
会将输入矩阵转换为如上所述的图形。创建此图后,可以在 top-left 节点上调用 shortestPathTo
方法。它returns一个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
的定义以尝试其他输入。
给定一个包含每个元素初始状态的矩阵,找到从左上角到右下角到达的最小步数?
条件:
任何元素的初始状态将随机为北、东、南或西之一。 在每一步,我们要么不移动任何地方,要么沿着该元素当前状态的方向移动(当然我们永远不会离开矩阵) 任何一步都会同时改变矩阵所有元素的状态。状态以顺时针循环方式变化,即从 N -> E -> S -> W。即使我们一步不移动,状态也会变化
一个重要的观察是矩阵有4个不同"versions":每4个步骤的倍数,矩阵的内容将完全相同。
您可以将这 4 个矩阵想象成三维 (Z-direction),其中 Z 可以是 0、1、2 或 3。将其想象成一个 3D 阵列,4 x 2D 阵列位于 each-other.
有了那个 3D 矩阵,"turning" 值的魔力消失了:这 4 个矩阵中的每一个现在都是静态的。
一个步骤现在是:
- 按照当前单元格内容指示的方向移动,因此 X 或 Y 发生变化,或者
- X 和 Y 保持不变的移动
...但在这两种情况下 Z 变为 (Z+1)%4
目标单元格现在实际上是一组 4 个单元格,因为到达 bottom-right 角时 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 = 西。
该算法由两个函数组成。一种是Nodeclass,shortestPathTo
的方法,它实现了从一个节点到一组目标节点的通用BFS搜索。第二个函数 createGraph
会将输入矩阵转换为如上所述的图形。创建此图后,可以在 top-left 节点上调用 shortestPathTo
方法。它returns一个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
的定义以尝试其他输入。