在二维数组中查找可用的"数字"

Question

我有这个问题,我需要以最有效的方式解决.我有一个2d数组,其中包含以下内容:1的所有内容都是"墙",这意味着您无法通过它.2是你输入数组或地图的入口,如果你愿意的话.3是我们需要找到的东西.以下是地图的示例:

1111111
1  3131
2 11111
1    31
1111111

这可能是我需要查看的数组的一个例子.正如你所看到的,有一个"无法访问,因为它被一个墙"1"包围.这意味着这个数组中有两个可用的数字.

首先,我们需要找到入口.由于入口可以在任何地方我需要搜索整个阵列.我做了以下事情:

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;
             }

         }

这需要O(n ^ 2)时间,我真的没有看到另一种方法,因为入口可以在任何地方.但是,我不确定如何有效和快速地找到可用的数字.我想在搜索数组的入口时,我会同时找到数组中的所有数字3,即使有些可能无法访问,之后我不确定如何有效地找到哪些是可访问的.

Answer 1

你不可能做得比 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)。