在javascript中返回指定图形的矩形序列的函数

Question

该图是由减号-、加号+、竖线|组成的ASCII多行字符串。和空格。任务是将图形分解成矩形。下面编写的函数无法按照要求正常工作。而且我找不到问题出在哪里。功能如下图

/**
 * Returns the rectangles sequence of specified figure.
 * The figure is ASCII multiline string comprised of minus signs -, plus signs +,
 * vertical bars | and whitespaces.
 * The task is to break the figure in the rectangles it is made of.
 *
 * NOTE: The order of rectangles does not matter.
 *
 * @param {string} figure
 * @return {Iterable.<string>} decomposition to basic parts
 *
 * @example
 *
 *    '+------------+\n'+
 *    '|            |\n'+
 *    '|            |\n'+        '+------------+\n'+
 *    '|            |\n'+        '|            |\n'+         '+------+\n'+          '+-----+\n'+
 *    '+------+-----+\n'+   =>   '|            |\n'+     ,   '|      |\n'+     ,    '|     |\n'+
 *    '|      |     |\n'+        '|            |\n'+         '|      |\n'+          '|     |\n'+
 *    '|      |     |\n'         '+------------+\n'          '+------+\n'           '+-----+\n'
 *    '+------+-----+\n'
 *
 *
 *
 *    '   +-----+     \n'+
 *    '   |     |     \n'+                                    '+-------------+\n'+
 *    '+--+-----+----+\n'+              '+-----+\n'+          '|             |\n'+
 *    '|             |\n'+      =>      '|     |\n'+     ,    '|             |\n'+
 *    '|             |\n'+              '+-----+\n'           '+-------------+\n'
 *    '+-------------+\n'
 */
function* getFigureRectangles(figure) {
  const lines = figure.split("\n");
  const rectangles = [];

  for (let y1 = 0; y1 < lines.length; y1++) {
    for (let x1 = 0; x1 < lines[y1].length; x1++) {
      if (lines[y1][x1] === "+") {
        for (let y2 = y1 + 1; y2 < lines.length; y2++) {
          for (let x2 = x1 + 1; x2 < lines[y1].length; x2++) {
            if (
              lines[y2][x2] === "+" &&
              lines[y1][x2] === "+" &&
              lines[y2][x1] === "+"
            ) {
              const rectangle = [];
              for (let y = y1; y <= y2; y++) {
                rectangle.push(lines[y].substring(x1, x2 + 1));
              }
              rectangles.push(rectangle);

              // Clear the rectangle from the figure
              for (let y = y1; y <= y2; y++) {
                lines[y] =
                  lines[y].substring(0, x1) +
                  " ".repeat(x2 - x1 + 1) +
                  lines[y].substring(x2 + 1);
              }
            }
          }
        }
      }
    }
  }

  for (const rectangle of rectangles) {
    yield rectangle.join("\n");
  }
}

Answer 1

算法很简单，逐行浏览图形，找到

(x0,y0)

边缘，然后在右侧找到

x1

边缘，向下到最近的底部边缘，找到

y1

。现在你有了

(x1,y1)

，假设这些是矩形边缘，因此通过运行一个函数来检查是否满足矩形的所有条件来验证它。在这种情况下：

• 所有角边缘应为

  '+'

• 高度边框的所有字符都应该是条形

  '|'

  。

注意：不要检查边缘上的

'-'

，因为某些矩形如果与其他较小的矩形接壤，则可以将

'+'

作为其边缘字符的一部分。

当所有这些检查都满足时，生成一个矩形绘图。您可以按照以下代码进行操作。

/**
 * Returns the rectangles sequence of specified figure.
 * The figure is ASCII multiline string comprised of minus signs -, plus signs +,
 * vertical bars | and whitespaces.
 * The task is to break the figure in the rectangles it is made of.
 *
 * NOTE: The order of rectanles does not matter.
 *
 * @param {string} figure
 * @return {Iterable.<string>} decomposition to basic parts
 *
 * @example
 *
 *    '+------------+\n'+
 *    '|            |\n'+
 *    '|            |\n'+        '+------------+\n'+
 *    '|            |\n'+        '|            |\n'+         '+------+\n'+          '+-----+\n'+
 *    '+------+-----+\n'+   =>   '|            |\n'+     ,   '|      |\n'+     ,    '|     |\n'+
 *    '|      |     |\n'+        '|            |\n'+         '|      |\n'+          '|     |\n'+
 *    '|      |     |\n'         '+------------+\n'          '+------+\n'           '+-----+\n'
 *    '+------+-----+\n'
 *
 *
 *
 *    '   +-----+     \n'+
 *    '   |     |     \n'+                                    '+-------------+\n'+
 *    '+--+-----+----+\n'+              '+-----+\n'+          '|             |\n'+
 *    '|             |\n'+      =>      '|     |\n'+     ,    '|             |\n'+
 *    '|             |\n'+              '+-----+\n'           '+-------------+\n'
 *    '+-------------+\n'
 */
/**
 * Generator function that yields rectangles found within a given ASCII figure.
 *
 * @param {string} figure - Multiline string representing the ASCII figure.
 * @return {Generator<string, void, unknown>} - Generator yielding each rectangle as a string.
 */
function* getFigureRectangles(figure) {
  const lines = figure.split("\n");
  const height = lines.length;
  const width = lines[0].length;

  for (let y = 0; y < height; y++) {
    for (let x = 0; x < width; x++) {
      if (lines[y][x] === "+") {
        for (let bottomY = y + 1; bottomY < height; bottomY++) {
          if (lines[bottomY][x] === "+") {
            for (let rightX = x + 1; rightX < width; rightX++) {
              if (lines[y][rightX] === "+") {
                if (lines[bottomY][rightX] === "+") {
                  if (isRectangle(lines, x, y, rightX, bottomY)) {
                    yield drawRectangle(rightX - x + 1, bottomY - y + 1);
                    rightX = width;
                    bottomY = height;
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}

/**
 * Checks if the specified area forms a valid rectangle.
 *
 * @param {string[]} lines - Array of strings representing the ASCII figure.
 * @param {number} startX - X-coordinate of the top-left corner.
 * @param {number} startY - Y-coordinate of the top-left corner.
 * @param {number} endX - X-coordinate of the bottom-right corner.
 * @param {number} endY - Y-coordinate of the bottom-right corner.
 * @return {boolean} - True if a valid rectangle is found, false otherwise.
 */
function isRectangle(lines, startX, startY, endX, endY) {
  for (let y = startY; y <= endY; y++) {
    for (let x = startX; x <= endX; x++) {
      if (y === startY || y === endY) {
        if ((x === startX || x === endX) && lines[y][x] !== "+") {
          return false;
        }
      } else {
        if (lines[y][x] === "+") {
          return false;
        }
        if ((x === startX || x === endX) && lines[y][x] !== "|") {
          return false;
        }
      }
    }
  }
  return true;
}

/**
 * Draws a rectangle based on the provided dimensions.
 *
 * @param {number} width - Width of the rectangle.
 * @param {number} height - Height of the rectangle.
 * @return {string} - String representing the drawn rectangle.
 */
function drawRectangle(width, height) {
  let rectangle = "+" + "-".repeat(width - 2) + "+\n";
  for (let y = 1; y < height - 1; y++) {
    rectangle += "|" + " ".repeat(width - 2) + "|\n";
  }
  rectangle += "+" + "-".repeat(width - 2) + "+\n";
  return rectangle;
}

const figure2 =
  "   +-----+     \n" +
  "   |     |     \n" +
  "+--+-----+----+\n" +
  "|             |\n" +
  "|             |\n" +
  "+-------------+\n";

for (const rectangle of getFigureRectangles(figure2)) {
  console.log(rectangle);
}