6

I have this problem that I need to solve in the most effecient way. I have a 2d array that contains the following: Everything that is a 1 is a "wall" which means you cannot go through it. 2 is the entrance where you "enter" the array or map if you like. 3 are the things we need to find. Here is an example of a map:

1111111
1  3131
2 11111
1    31
1111111

This could be an example of an array that i need to look in. As you can see there is a 3 that is "unreachable, since it's surrounded by a wall "1". Which means that there are two available numbers in this array.

First we need to find the entrance. Since the entrance can be anywhere I need to search the entire array. I have done the following:

int treasureAmount = 0;
     Point entrance = new Point(0,0);
     for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; i++){
             if(map[i][j] == 2){
                 entrance.x =i;
                 entrance.y =j;
             }

         }

This takes O(n^2) time, and i don't really see another way to do this, since the entrance can be anywhere. However i'm not really sure how to find the available numbers effectivly and fast. I thought about while searching the arrays for the entrance i will at the same time find the all the number 3 in the array even though some might not be accessible, and after that i'm not really sure how to effectivly find which are accessible.

4

3 回答 3

2

你不能比 O(n^2) 做得更好。仅仅读取数组就需要这么多时间。但随后您可以进行深度优先搜索以在数组中找到可到达的 3。这是伪代码。

main()
{
    read array and mark the entrance as ent.x and ent.y and also an array threex[] and threey[] that stores all the exit position.
    boolean visited[][]; //stores whether array[i][j] is reachable or not.
    dfs(ent.x,ent.y);
    for each element in three arrays
    {
        if(visited[threex[i]][threey[i]]) print ("Reachable");
        else print("not reachable", threex[i], threey[i]);
    }
}
int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; // dx[i], dy[i] tells whether to move in E,N,W,S respectively.
dfs(int x,int y)
{
    visited[x][y]=true;
    for(i=0;i<4;i++)//move in all directions
    {
        int newx=x+dx[i],newy=y+dy[i];
        //check if this is within the array boundary
        if(newx>=0&&newx<N && newy>=0&&newy<N)
        if(!visited[newx][newy] && array[newx][newy]!=1) // check if the node is unvisited and that it is pemissible
             dfs(newx,newy);
    }
}

由于每个数组元素在 dfs 函数中被占用不超过一次，因此代码的复杂度为 O(n^2)。

于 2013-04-25T11:40:45.860 回答
0

由于入口项和目标项都可以位于数组中的任何位置，因此您别无选择，只能搜索所有内容。因此，您的入口搜索尽可能高效，关于目标项目，我推荐迷宫洪水填充算法。

然而，该算法的链接版本偏向于一个方向（就像它正在用水填充它，它会“向下”泛滥）。为了尽可能高效，您应该让它向各个方向扩展（就像您正在用气体填充它），例如：

            2
      1    212
0    101  21012
      1    212
            2

数字代表扩展的迭代。扩展是在四个方向上进行的：左、右、上和下。当你到达目标item时，只需回溯到迭代索引小于1的相邻cell邻居，就可以找到最短路径，直到返回到0迭代索引——入口。

于 2013-04-25T11:52:44.517 回答
0

创建数组时，您可以保留值为 2 的坐标列表。您可以在 O(n) 中遍历该列表。

于 2013-04-25T11:23:59.420 回答