java - 在二维数组中查找可用的 "number"

Question

我有这个问题需要以最有效的方式解决。我有一个包含以下内容的二维数组:所有为 1 的东西都是一堵“墙”，这意味着你无法穿过它。 2 是您“输入”数组或映射(如果您愿意)的入口。 3 是我们需要找到的东西。这是 map 的示例:

1111111
1  3131
2 11111
1    31
1111111

这可能是我需要查看的数组示例。如您所见，有一个“无法到达，因为它被墙“1”包围的 3”。这意味着有两个可用数字这个数组。

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

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)。