3

假设我有一张用 ASCII 写的地图。这张地图代表了一些人的花园。我必须编写一个程序，给定地图返回每个花园中有多少棵树。样机地图：

+-----------+------------------------------------+
|           |    B  A                            |
|  A A A A  |     A       (Jennifer)             |
|           |                                    |
|     C     +--------------+---------------------+
|       B        C         |                     |
|   B       C              |                B B  |
|     B       C            |    (Marta)          |
|         B                |                     |
+--------------+           |                     |
|              |           |                     |
| (Peter) B    |           |             A       |
|   C          |  (Maria)  |                     |
|     A        |           |                     |
+--------------+           +---------------------+
|              |           |                     |
|              |           |                     |
|              |           |                     |
| (Elsa)       +           |      (Joe)          |
|             /            |        C            |
|   C  A     /      A      +      C   A    A     |
|    B      /     A   B     \     A   B          |
|     B A  /        C        \           B       |
+---------+----+---------- +--+------------------+

输出应该是这样的：

Jennifer B:1 A:1 C:0
Marta    B:2 A:1 C:0
Peter    A:1 B:1 C:1
...
Joe      A:3 B:2 C:2

python中是否有任何包或我可以研究以了解如何执行此任务的任何算法？

4

2 回答 2

1

我将开始从该 ascii 创建一个字符矩阵。

然后我会找到'（'的所有（i，j）。

发现索引可以创建一个字典，其中人的名字作为键，另一个字典作为值。每个内部字典都将以树名作为键，以整数作为值。

知道'（'的（i，j）我会阅读名称并初始化字典。

现在，foreach (i,j) 指向一个 '(' do: (let name是与 '('

  • che if 在 '(' 的左边有一个字母。如果你找到一个字母x让dict[name][x]++ (如果你找到任何一个 ('|','','/',' 就停止+')
  • 对右边做同样的事情
  • 开始向上，为每一行检查左右
  • 向下时做同样的事情

你只需要玩一点就可以了解如何正确识别玛丽亚和珍妮弗之间的墙。

于 2020-07-15T18:35:30.133 回答
0

这是一个 JavaScript 示例，应该很容易转换为 Python。它根据当前标记区域的确定从左到右扫描。希望函数名称和注释能够清楚地说明它发生了什么。如果您有任何问题，请询问。

function f(map){
  const m = map.split('\n')
    .filter(x => x)
    .map(x => x.trim());
    
  const [h, w] = [m.length, m[0].length];
  
  const borders = ['+', '-', '|', '/', '\\'];
  const trees = ['A', 'B', 'C'];
  
  const labelToName = {};
  const result = {};
  
  let prevLabels = new Array(w).fill(0);
  let currLabels = new Array(w).fill(0);
  let label = 1;
  
  function getLabel(y, x){
    // A label is the same as
    // a non-border to the left,
    // above, or northeast.
    if (!borders.includes(m[y][x-1]))
      return currLabels[x-1];
    else if (!borders.includes(m[y-1][x]))
      return prevLabels[x];
    else if (!borders.includes(m[y-1][x+1]))
      return prevLabels[x+1];
    else
      return label++;
  }
  
  function update(label, tree){
    if (!result[label])
      result[label] = {[tree]: 1};
    else if (result[label][tree])
      result[label][tree]++;
    else
      result[label][tree] = 1;
  }
  
  for (let y=1; y<h-1; y++){
    for (let x=1; x<w-1; x++){
      const tile = m[y][x];
      
      if (borders.includes(tile))
        continue;
        
      const currLabel = getLabel(y, x);
      currLabels[x] = currLabel;
      
      if (tile == '('){
        let name = '';
        while (m[y][++x] != ')'){
          name += m[y][x];
          currLabels[x] = currLabel;
        }
        currLabels[x] = currLabel;
        labelToName[currLabel] = name;
      
      } else if (trees.includes(tile)){
        update(currLabel, tile);
      }
    }
    
    prevLabels = currLabels;
    currLabels = new Array(w).fill(0);
  }
  
  return [result, labelToName];
}

var map = `
    +-----------+------------------------------------+
    |           |    B  A                            |
    |  A A A A  |     A       (Jennifer)             |
    |           |                                    |
    |     C     +--------------+---------------------+
    |       B        C         |                     |
    |   B       C              |                B B  |
    |     B       C            |    (Marta)          |
    |         B                |                     |
    +--------------+           |                     |
    |              |           |                     |
    | (Peter) B    |           |             A       |
    |   C          |  (Maria)  |                     |
    |     A        |           |                     |
    +--------------+           +---------------------+
    |              |           |                     |
    |              |           |                     |
    |              |           |                     |
    | (Elsa)       +           |      (Joe)          |
    |             /            |        C            |
    |   C  A     /      A      +      C   A    A     |
    |    B      /     A   B     \\     A   B          |
    |     B A  /        C        \\           B       |
    +---------+----+---------- +--+------------------+
`;

var [result, labelToName] = f(map);
for (let label in result)
  console.log(`${ labelToName[label] }: ${ JSON.stringify(result[label]) }`)

于 2020-07-16T17:33:12.377 回答