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.