CODEWITHSUNDEEP
javaalgorithm
Christian A
Christian A

Reputation: 501

Find available "number" in a 2d array

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.

Upvotes: 6

Views: 542

Answers (3)

linski
linski

Reputation: 5094

Since both entrance and target items can be anywhere in the array you don't have much choice, but to search everything. So, your entrance search is as efficient as it can be, and regarding the target items I recommend the maze flood fill algorithm.

However, the linked version of the algorithm favorizes one direction (like it is filling it with water, it floods "down"). To be as efficient as it can, you should make it expand in all directions (like you're filling it with gas), e.g.:

            2
      1    212
0    101  21012
      1    212
            2

The numbers represent the iterations of expansion. The expansion is made in four directions: left, right, up and down. When you reach the target item, you can find the shortest route simply by backtracking to the adjacent cell neighbour whose iteration index is lesser by one, until you return to the 0 iteration index - the entrance.

Upvotes: 0

Wayne Rooney
Wayne Rooney

Reputation: 1607

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

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

Upvotes: 2

Amir Kost
Amir Kost

Reputation: 2168

When creating the array, you can keep a list of coordinates of that have the value of 2. You can traverse that list in O(n).

Upvotes: 0

Related Questions