Find the "number" in a 2d array

Question

I have this problem that I need to solve in the most efficient way. I have a 2d array that contains the following: All that is 1 is a “wall”, which means you cannot go through it. 2 is the input where you "enter" the array or map, if you want. 3 is what we need to find. Here is an example map:

1111111 1 3131 2 11111 1 31 1111111 

This might be an example of an array that I need to look into. As you can see, there are 3 that are “inaccessible, since they are surrounded by a wall of“ 1. ”This means that there are two numbers available in this array.

First we need to find the entrance. Since the input 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; } } 

It takes O (n ^ 2) time, and I see no other way to do this, since the input can be anywhere. However, I am not sure how to quickly and quickly find the available rooms. I was thinking that when searching for arrays to enter, at the same time I will find all the number 3 in the array, although some may not be available, and after that I am not quite sure how to efficiently find available ones.

Answer 1

You cannot do it better than O (n ^ 2). It takes a long time to read the array. But then you can do the first depth search to find reachable 3 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 element of the array takes no more than once in the dfs function, the complexity of the code is O (n ^ 2).

Answer 2

When you create an array, you can save a list of coordinates of value 2. You can cross this list in O (n).

Answer 3

Since both input and target elements can be anywhere in the array, you do not have much choice, but to search for everything. Thus, your input search is as efficient as possible, and I recommend the maze fill algorithm for targets.

However, the associated version of the algorithm favors one direction (for example, it fills it with water, it floods "down"). To be as effective as possible, you must expand it in all directions (for example, you fill it with gas), for example:

  2 1 212 0 101 21012 1 212 2 

Numbers are iterations of expansion. Expansion is performed in four directions: left, right, up and down. When you reach the target, you can find the shortest route simply by looking at the neighboring neighbors juice, whose iteration index is less than one, until you return to iteration index 0 - to the input.