A return 地图中的树数

Question

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

+-----------+------------------------------------+
|           |    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 中是否有任何包或任何我可以学习以了解如何执行此任务的算法？

Answer 1

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

然后我会找到 '(' 的所有 (i,j)。

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

知道 '(' 的 (i,j) 我会读取名称并初始化字典。

现在，指向 '(' 的 foreach (i,j) 做：(设 name 为与 '('

相关的名称

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

你只要玩一下就能明白如何正确识别玛丽亚和詹妮弗之间的墙。

Answer 2

这是 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]) }`)

A return 地图中的树数

A return the number of trees in a map

python

algorithm

ascii

ascii-art