3

草书文字：较早的条目

普通文本：最新条目

好的，所以我有一个 2D 整数数组，更具体地说，是 0 和 1。最初这是一个 BMP 文件（黑白），我将其转换为一个整数数组。现在，矩阵表示一张地图，其中 0 是我可以站立的位置（如果你愿意的话，可以是地板），而 1 是深渊或墙壁（你不能站在 1 中）。所以我需要通过这个随机的整数数组，但我需要能够通过地图的所有 0。我是否多次访问“像素”都没关系这有什么意义？我有一种方法可以“隐藏”地图中的 4 个键，我的角色必须在地图中找到它们。我的角色只能上下左右移动。不允许对角线移动，显然也不允许传送。到目前为止，我有这个代码：

public void goThrough(int[,] map, int[] pos)
{
    int i = pos[0], j = pos[1]  ;
    while( i < map.GetLength(0) && j < map.GetLength(1) )
    {
        int cont = 0;
        if (map[i, j] == 0) 
        { 
            if (map[i, j + 1] == 0 && cont == 0 ) { j++; cont++; }
            if (map[i + 1, j] == 0 && cont == 0) { i++; cont++; }
            if (map[i, j - 1] == 0 && cont == 0 ) { j--; cont++; }
            if (map[i - 1, j] == 0 && cont == 0 ) { i--; cont++; }
        }
        if (map[i, j] == 1)
        {
        }
    }
}

public int[] Position(int[,] map)
{
    int[] pos = { 0, 0 };

    for (int i = 0; i < map.GetLength(0) && map[pos[0], pos[1]] == 1; i++)
    {
        for (int j = 0; j < map.GetLength(1) && map[pos[0], pos[1]] == 1; j++)
        {
            pos[0] = i;
            pos[1] = j;
        }
    }
    return pos;
}

它显然有一些错误。请发送一些反馈！也许对这种代码有一些经验的人可以帮助我一点：D。

Edit1：很抱歉我没有指定语言。这是 C#。为了快速更新：我尝试创建另一个 int[,] （与第一个完全相同），每次我的“资源管理器”通过任何 (x,y) 时，我都会在这个位置添加一个 (1) （第二个，复制的）数组。通过这种方式，我可以制作一种方法来识别我何时完全“探索”地图。此外，使用这个“复制”数组，如果我处于探索者之前的位置，我可以选择另一个方向（那个点在第二个数组中不会是 0，实际上，每次探索者经过那个点时，它将向数组中的该位置添加一 (1)）。这个想法是让探险者在经过同一个地点一次、两次或更多次时表现不同……但所有这些都不起作用。我'

EDIT2：现在我有这个代码：

    public void goThrough(int[,] map, int[] pos, bool[,] visited)
    {
        int x = pos[0];
        int y = pos[1];
        visited[x, y] = true;
        Console.WriteLine("Position -> Column: {0} || Row: {1}", x, y);
        // ShowAtPosition(x, y)
        if (y > 0 && map[x, y - 1] == 0 && !visited[x, y - 1])
        {
            goThrough(map, new[] { x, y + 1 },visited); // north
            // ShowAtPosition(x, y)
        }
        if (x < map.GetLength(0) - 1 && map[x + 1, y] == 0 && !visited[x + 1, y])
        {
            goThrough(map, new[] { x + 1, y }, visited); // east
            // ShowAtPosition(x, y)
        }
        if (y < map.GetLength(1) - 1 && map[x, y + 1] == 0 && !visited[x, y + 1])
        {
            goThrough(map, new[] { x, y - 1 }, visited); // south
            // ShowAtPosition(x, y)
        }
        if (x > 0 && map[x - 1, y] == 0 && !visited[x - 1, y])
        {
            goThrough(map, new[] { x - 1, y }, visited); // west
            // ShowAtPosition(x, y)
        }
        if (NoZeros(visited)) { Console.WriteLine("I went through everything!"); Console.ReadLine(); }


    }

请注意我放置的 WriteLine，因此我可以跟踪此递归方法的每次迭代。这是输出：

Position -> Column: 1 || Row: 31
Position -> Column: 2 || Row: 31
Position -> Column: 3 || Row: 31
Position -> Column: 4 || Row: 31
Position -> Column: 5 || Row: 31
Position -> Column: 6 || Row: 31
Position -> Column: 7 || Row: 31
Position -> Column: 8 || Row: 31
Position -> Column: 9 || Row: 31
Position -> Column: 10 || Row: 31
Position -> Column: 10 || Row: 32
Position -> Column: 11 || Row: 31
Position -> Column: 12 || Row: 31
Position -> Column: 13 || Row: 31
Position -> Column: 13 || Row: 32
Position -> Column: 14 || Row: 31
Position -> Column: 15 || Row: 31
Position -> Column: 16 || Row: 31
Position -> Column: 16 || Row: 32
Position -> Column: 17 || Row: 31
Position -> Column: 18 || Row: 31
Position -> Column: 19 || Row: 31
Position -> Column: 20 || Row: 31
Position -> Column: 21 || Row: 31
Position -> Column: 22 || Row: 31
Position -> Column: 23 || Row: 31
Position -> Column: 24 || Row: 31
Position -> Column: 25 || Row: 31
Position -> Column: 25 || Row: 30
Position -> Column: 1 || Row: 30

所以，首先，这个方法没有穿过所有的迷宫，甚至没有关闭（是的，0 都是连接的）。

其次，在最后一次迭代中（输出的最后 2 行），资源管理器从 (25,30) “传送”到 (1,30)。

顺便说一句，这是图像：

白色 =0 和黑色 =1

4

2 回答 2

3

起初听起来你只是在寻找一个解决迷宫的算法；类似于左手墙的追随者。

但是，您不是在寻找走出迷宫的路径，而是在寻找具有相同值的所有连续位置。所以基本上你可以使用洪水填充算法。

唯一的问题是您可能有多个0未连接的 s 池（除非您的原始位图被构造为使所有 0 都被连接，在这种情况下，您可以确保所有键都可以通过只放置它们来访问0 个细胞）。因此，您可能需要从多个起点进行洪水填充，以确保覆盖所有内容。

于 2013-04-21T22:51:12.597 回答
1

您可以创建一棵树，其中包含您遇到的所有可能路径。每个节点代表地图中的某个点，所有子节点代表您可以前往的有效点。每个访问过的点都被标记，这样您就不会再次尝试访问它。如果您随后执行深度优先树搜索，您可以四处走动，直到您探索完所有可能的位置。每当您遇到访问过的节点时，您都​​不会再去那里。下面执行递归深度优先搜索。对于大型地图，您将需要一个非递归解决方案，否则您将获得 StackOverflowException。

private bool[,] visited; // needs to have same size as map
public void GoThrough(int[,] map, int[] pos) {
  int x = pos[0];
  int y = pos[1];
  visited[x, y] = true;
  // ShowAtPosition(x, y)
  if (y > 0 && map[x, y - 1] == 0 && !visited[x, y - 1]) {
    GoThrough(map, new [] {x, y - 1}); // north
    // ShowAtPosition(x, y)
  }
  if (x < map.GetLength(0) - 1 && map[x + 1, y] == 0 && !visited[x + 1, y]) {
    GoThrough(map, new [] {x + 1, y}); // east
    // ShowAtPosition(x, y)
  }
  if (y < map.GetLength(1) - 1 && map[x, y + 1] == 0 && !visited[x, y + 1]) {
    GoThrough(map, new [] {x, y + 1}); // south
    // ShowAtPosition(x, y)
  }
  if (x > 0 && map[x - 1, y] == 0 && !visited[x - 1, y]) {
    GoThrough(map, new [] {x - 1, y}); // west
    // ShowAtPosition(x, y)
  }
}

它将遍历整个地图和所有可到达的图块，然后返回起点。

本质上，这是 Matthew Strawbridge 提到的洪水填充算法（当我输入答案时）。

于 2013-04-21T22:57:06.793 回答