Tìm "số" có sẵn trong mảng 2d

Question

Tôi có vấn đề này mà tôi cần phải giải quyết theo cách hiệu quả nhất. Tôi có một mảng 2d có chứa các thông tin sau: Mọi thứ là 1 là "bức tường" có nghĩa là bạn không thể đi qua nó. 2 là lối vào nơi bạn "nhập" mảng hoặc bản đồ nếu bạn muốn. 3 là những thứ chúng ta cần tìm. Dưới đây là một ví dụ về một bản đồ:

1111111 
1 3131 
2 11111 
1 31 
1111111 

Đây có thể là một ví dụ về một mảng mà tôi cần phải xem xét trong Như bạn có thể thấy có một 3 đó là "không thể kết nối, vì nó được bao quanh bởi một bức tường". .... 1" Điều đó có nghĩa rằng có hai số có sẵn trong mảng này

tiên chúng ta cần phải tìm lối vào Từ lối vào có thể được bất cứ nơi nào tôi cần phải tìm kiếm toàn bộ mảng tôi đã làm như sau:

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

     } 

Điều này cần thời gian O (n^2) và tôi không thực sự thấy một cách khác để thực hiện việc này, vì lối vào có thể ở bất cứ đâu. Tuy nhiên tôi không thực sự chắc chắn làm thế nào để tìm thấy những con số có sẵn effectivly và nhanh chóng. Tôi đã nghĩ đến khi tìm kiếm mảng cho lối vào, tôi sẽ tìm thấy tất cả số 3 trong mảng mặc dù một số có thể không truy cập được, và sau đó tôi không thực sự chắc chắn cách tìm kiếm có thể truy cập được.

Answer 1

Bạn không thể làm tốt hơn O (n^2). Nó sẽ mất nhiều thời gian chỉ để đọc mảng. Nhưng sau đó bạn có thể thực hiện tìm kiếm độ sâu đầu tiên để tìm 3 có thể truy cập trong mảng. Đây là mã giả.

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

Vì mỗi phần tử mảng được lấy không quá một lần trong hàm dfs độ phức tạp của mã là O (n^2).

Answer 2

Khi tạo mảng, bạn có thể giữ danh sách tọa độ có giá trị là 2. Bạn có thể duyệt danh sách đó trong O (n).

Answer 3

Vì cả mục nhập và mục tiêu đều có thể ở bất kỳ đâu trong mảng mà bạn không có nhiều lựa chọn, nhưng để tìm kiếm mọi thứ. Vì vậy, tìm kiếm lối vào của bạn là hiệu quả như nó có thể được, và liên quan đến các mục tiêu tôi khuyên bạn nên maze flood fill algorithm.

Tuy nhiên, phiên bản được liên kết của thuật toán ưu tiên một hướng (giống như đang đổ đầy nước, nó tràn "xuống"). Để hiệu quả nhất có thể, bạn nên làm cho nó mở rộng theo mọi hướng (như bạn đang đổ đầy khí đốt), ví dụ:

  2 
     1 212 
0 101 21012 
     1 212 
      2 

Các con số đại diện cho các lần lặp mở rộng. Việc mở rộng được thực hiện theo bốn hướng: trái, phải, lên và xuống. Khi bạn đạt được mục tiêu, bạn có thể tìm thấy tuyến đường ngắn nhất đơn giản bằng cách quay lại hàng xóm lân cận có chỉ số lặp lại ít hơn một, cho đến khi bạn quay trở lại chỉ số lặp 0 - lối vào.