确定网格上的一系列移动是否形成矩形

问题描述 投票：0回答：4

我正在尝试解决这个编码挑战：

绘图机器人位于坐标平面的 (0,0) 点，字符串 

moves
描述了机器人将采取的路径。

字符串的每个字符都描述机器人所做的单个动作。此外，机器人还会做出动作 与它们在字符串中出现的顺序完全相同，从位置 (0,0) 开始。假设机器人已经 从字符串中进行了一些移动，并且当前位于点 (x,y)，如果字符串的下一个字符是：

  • “^”：机器人将移动到(x,y+1)，
  • “v”：机器人将移动到(x,y-1)，
  • ”<": the robot will move to (x-1,y),
  • ">"：机器人将移动到(x+1,y)。

机器人每次移动时，都会在当前位置和移动到的点之间画一条线。确保字符串 

moves
中提供的指令永远不会导致机器人多次访问同一点，但点 (0,0) 除外，机器人可能会访问该点两次： 机器人路径的起点和终点。任务是确定机器人完成字符串中提供的所有动作后，它绘制的所有线条是否形成一个矩形。

编写一个函数：

function solution(moves)
：给定字符串
moves
，如果机器人的路径将形成矩形，则返回 true，否则返回 false。

  • 鉴于 
    moves="^^^<<<<vvv>>>>"
    ，该函数应返回 true。
  • 鉴于 
    moves="<vvv>>^^^<"
    ，该函数应返回 true。

假设：

  • 字符串
    moves
    的长度在[1...100]范围内。
  • 字符串
    moves
    仅由以下字符组成：“^”、“v”、“<" and/or ">”。
  • 机器人不会两次访问同一个点，除了点 (0,0)，该点可能会在机器人路径的起点和终点被访问。

这是我写的代码，它仅用于检查形状是正方形还是矩形， 但它无法判断形状是否有更多匝数，同时高度和宽度仍然不同， 例如，

moves="^^^^^^<<<<vv>>v<<vvv>>>>";
不会形成一个矩形，但因为它有 两边高度相同，算作矩形。

const moves = "^^^<<<<vvv>>>>";
console.log(solution(moves));
function solution(moves) {
  let xPos = 0,
    yPos = 0;
  let xMin = 0,
    xMax = 0,
    yMin = 0,
    yMax = 0;
  let visited = new Set();
  visited.add("0,0");
  for (let i = 0; i < moves.length; i++) {
    let movement = moves[i];
    if (movement === "<") {
      xPos--;
      xMin = Math.min(xMin, xPos);
    } else if (movement === ">") {
      xPos++;
      xMax = Math.max(xMax, xPos);
    } else if (movement === "^") {
      yPos++;
      yMax = Math.max(yMax, yPos);
    } else if (movement === "v") {
      yPos--;
      yMin = Math.min(yMin, yPos);
    }
    let currPos = `${xPos},${yPos}`;
    visited.add(currPos);
  }
  if (xPos !== 0 || yPos !== 0) return false;
  const width = xMax - xMin + 1;
  const height = yMax - yMin + 1;
  console.log(visited);
  if (width > height || height > width) return true;
  else return false;
}

我想知道我需要什么操作才能确保只有在形成矩形时才返回true。

javascript algorithm math geometry
4个回答
0
投票

检查这个：

function solution(moves) {
      let xPos = 0,
        yPos = 0;
      let xMin = 0,
        xMax = 0,
        yMin = 0,
        yMax = 0;
      let visited = new Set();
      visited.add("0,0");
      let leftTurns = 0;
      let rightTurns = 0;
      
      for (let i = 0; i < moves.length; i++) {
        let movement = moves[i];
        if (movement === "<") {
          xPos--;
          xMin = Math.min(xMin, xPos);
          leftTurns++;
        } else if (movement === ">") {
          xPos++;
          xMax = Math.max(xMax, xPos);
          rightTurns++;
        } else if (movement === "^") {
          yPos++;
          yMax = Math.max(yMax, yPos);
        } else if (movement === "v") {
          yPos--;
          yMin = Math.min(yMin, yPos);
        }
        let currPos = `${xPos},${yPos}`;
        visited.add(currPos);
      }
      
      if (xPos !== 0 || yPos !== 0) return false;
      const width = xMax - xMin + 1;
      const height = yMax - yMin + 1;
      
      if (width > height || height > width) return false;
      if (visited.size !== (width + 1) * (height + 1)) return false;
      if (leftTurns !== rightTurns) return false;
      
      return true;
    }
0
投票

我在这里看到了一些东西。

  1. 要成为矩形，“<" and ">”的数量必须匹配，“^”和“v”的数量也必须匹配。
  2. 所有转换必须是从（“<" or ">”）到（“^”或“v”）或（“^”或“v”）到（“<" or ">”）
  3. 转换数量必须为 3，但如果第一个和最后一个方向匹配，也可以为 4。

我认为你的代码可能处理#1，也许你的验证处理#2。 对于#3，试试这个：

// 假设上面#1已经被确认了

const moves='^^^^^^<<<<vv>>v<<vvv>>>>';//"^^^<<<<vvv>>>>";
    function testit() {
        alert(solution(moves));
        alert(checkTransitionCount(moves));
    }
//function solution(moves){...this is your code...}

function checkTransitionCount(moves) {
  let transitionCount = 0;
  let nextChar = moves[0];
  for (let idx = 1; idx < moves.length; idx++) {
    if (nextChar != moves[idx]) {
      transitionCount++;
      nextChar = moves[idx];
    }
  }
  if (transitionCount == 3)
    return true;
  if (transitionCount  == 4)
    if (moves[0] == moves[moves.length - 1])
      return true;

  return false;
}

0
投票

空字符串对应于可以被视为零面积矩形的点。除此之外，输入定义一个矩形当且仅当：

  • 所有四个符号均出现，并且是连续的（环绕）。
  • 您有相同数量的相反符号
  • 对面并不相邻。

为了避免担心回绕，请移动输入字符串，以便移动字符串的第一个 elt 是输入的第二个不同的 elt。

我将使用 e1、e2、e3 和 e4 来引用您在移位字符串中遇到的第一个、第二个、第三个和第四个不同元素。

然后用你移动的字符串：

  • 计算 e1 连续出现的次数，称之为 k1。
  • 如果 e2 不存在或者与 e1 相反，则返回 False。
  • 计算 e2 连续出现的次数，称之为 k2。
  • 如果 e3 不存在或不是 e1 的相反，则返回 False。
  • 计算 e3 的连续出现次数，并返回 False，除非它等于 k1。
  • 如果 e4 不存在或者不是 e2 的相反，则返回 False。
  • 计算 e4 的连续出现次数，并返回 False，除非它等于 k1。
  • 如果尚未到达字符串末尾，则返回 False。
  • 返回真。
0
投票

为了有效，这一系列动作应该具有：

  • 无回溯，即执行与前一个动作相反的动作
  • 四个角，即应该有四个到不同移动的过渡，包括最后一个移动和第一个移动之间的潜在过渡。如果空输入被认为是可以接受的，那么这应该是一个例外。
  • 从开始的地方结束，即它应该具有相同数量的上下移动，以及相同数量的左右移动。

这是带有一些测试用例的实现：

const opposites = { "^": "v", ">": "<", "v": "^", "<": ">" };

function solution(moves) {
    if (!moves) return true; // Or false. Whatever is expected for empty input string
    let corners = 4;
    const counters = { "^": 0, ">": 0, "v": 0, "<": 0 };
    let prev = moves.at(-1);
    for (let i = 0; i < moves.length; i++) {
        let current = moves[i];
        counters[current]++;
        if (current !== prev) {
            corners--;
            if (corners < 0 || opposites[prev] === current) return false;
        }
        prev = current;
    }
    return corners === 0 && counters["^"] === counters["v"] && counters[">"] === counters["<"];
}

const tests = [
    ["^^^<<<<vvv>>>>", true],
    ["^^<<<<vvv>>>>^", true],
    ["^^^>>>>vvv<<<<", true],
    ["^^>>>>vvv<<<<^", true],
    ["^^^<<<<vv>>v>>", false], // Too many corners
    ["^^<<<<vvv>^>>>", false], // Too many corners
    ["^^>>vv<<^^>>vv<<", false], // Too many corners
    ["^^vvv>>>><<<<^", false], // Backtracking
    ["^^^>>>><<<<vvv", false], // Backtracking
    ["^^>>>>vvv<<^", false],  // Not arriving at (0, 0)
    ["^^>>>>vvvv<<<<^", false],  // Not arriving at (0, 0)
];

for (const [moves, expected] of tests) {
    console.log(moves, "got", solution(moves), "expected", expected);
}

另一种使用正则表达式的解决方案：更优雅，但效率稍低：

function solution(moves) {
    if (!moves) return true; // Or false. Whatever is expected for empty input string
    if (/\^v|v^|<>|></.test(moves)) return false; // Backtracking moves detected
    const sides = moves.match(/(.)\1*/g).map(({length}) => length);
    if (sides.length === 5 && moves.at(-1) === moves[0]) sides[0] += sides.pop();
    return sides.length === 4 && sides[0] === sides[2] && sides[1] === sides[3];
}

const tests = [
    ["^^^<<<<vvv>>>>", true],
    ["^^<<<<vvv>>>>^", true],
    ["^^^>>>>vvv<<<<", true],
    ["^^>>>>vvv<<<<^", true],
    ["^^^<<<<vv>>v>>", false], // Too many corners
    ["^^<<<<vvv>^>>>", false], // Too many corners
    ["^^>>vv<<^^>>vv<<", false], // Too many corners
    ["^^vvv>>>><<<<^", false], // Backtracking
    ["^^^>>>><<<<vvv", false], // Backtracking
    ["^^>>>>vvv<<^", false],  // Not arriving at (0, 0)
    ["^^>>>>vvvv<<<<^", false],  // Not arriving at (0, 0)
];

for (const [moves, expected] of tests) {
    console.log("got", solution(moves), "expected", expected);
}

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.