查找可用＆QUOT;数量＆QUOT;在一个二维数组 [英] Find available "number" in a 2d array

问题描述

我有这个问题，我需要解决的最effecient方式。 我有一个二维数组，它包含以下内容： 一切，这是一个1是墙，这意味着你可以不经过它。 2是你中输入数组或地图，如果你喜欢的入口。 3是我们需要找到的东西。这里是一个地图的一个例子：

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

这可能是我需要的都在数组的例子。正如你可以看到有一个3是无法访问，因为它的四周墙壁1，这意味着有两种可供选择的数字此阵。

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

         }

这需要为O（n ^ 2）的时候，我真的没有看到另一种方式来做到这一点，因为入口可以在任何地方。 但是我真的不知道如何找到可用号码用途不同，快捷。我想到了，而搜索阵列的入口，我将在同一时间找到所有的数字3的​​阵列中，即使一些可能无法访问，之后，我真的不知道怎么用途不同发现是访问。

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.

推荐答案

您不能做的更好的为O（n ^ 2）。这将需要那么多的时间只是为了读阵列。但你可以做一个深度优先搜索，找到可达3的到数组中。这里是伪code。

You cannot do it better that O(n^2). It will take that much time just to read the array. But then you could do a depth first search to find the reachable 3's in the array. Here is the pseudo code.

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功能的code复杂度为O（n ^ 2）。

Since each array element is taken up not more than once in the dfs function the complexity of the code is O(n^2).

这篇关于查找可用＆QUOT;数量＆QUOT;在一个二维数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！