2 डी सरणी

Question

में उपलब्ध "संख्या" खोजें मुझे यह समस्या है कि मुझे सबसे प्रभावशाली तरीके से हल करने की आवश्यकता है। मेरे पास 2 डी सरणी है जिसमें निम्न शामिल हैं: सब कुछ जो 1 है वह एक "दीवार" है जिसका अर्थ है कि आप इसके माध्यम से नहीं जा सकते हैं। 2 प्रवेश द्वार है जहां आप चाहें तो सरणी या मानचित्र "दर्ज करें"। 3 वे चीजें हैं जिन्हें हमें ढूंढने की ज़रूरत है। ।

1111111 
1 3131 
2 11111 
1 31 
1111111 

यह एक सरणी है कि मैं ", नहीं पहुंचा जा सकता क्योंकि यह एक दीवार से घिरा हुआ है" में देख कर वहाँ के रूप में आप देख सकते हैं एक 3 वह यह है कि जरूरत का एक उदाहरण हो सकता है: यहाँ एक नक्शा का एक उदाहरण है ।।।।

: 1 "इसका मतलब है कि इस सरणी में दो उपलब्ध नंबर दिए गए हैं कि

पहले हम प्रवेश द्वार खोजने की जरूरत है के बाद से प्रवेश द्वार कहीं भी मैं पूरी सरणी खोज करने की आवश्यकता हो सकता है मैं निम्नलिखित किया है

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

     } 

यह ओ (एन^2) समय लेता है, और मुझे वास्तव में ऐसा करने का कोई और तरीका नहीं दिखता है, क्योंकि प्रवेश कहीं भी हो सकता है। हालांकि मुझे वास्तव में यह सुनिश्चित नहीं है कि उपलब्ध संख्याओं को प्रभावी ढंग से और तेज़ी से कैसे ढूंढें। मैंने प्रवेश के लिए सरणी खोजते समय सोचा था कि मैं एक ही समय में सरणी में सभी नंबर 3 ढूंढूंगा, भले ही कुछ पहुंच योग्य न हों, और इसके बाद मुझे सच में यकीन नहीं है कि कैसे सुलभ रूप से सुलभ हो सकते हैं।

Answer 1

आप इसे बेहतर नहीं कर सकते हैं कि ओ (एन^2)। सरणी को पढ़ने में बस इतना समय लगेगा। लेकिन फिर आप सरणी में पहुंचने योग्य 3 के खोजने के लिए पहली बार गहराई से खोज कर सकते हैं। छद्म कोड यहाँ है।

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 की तुलना में अधिक लिया जाता है से काम कोड की जटिलता हे है (एन^2)।

Answer 2

सरणी बनाते समय, आप उस के निर्देशांक की एक सूची रख सकते हैं जिसका मूल्य 2 है। आप ओ (एन) में उस सूची को पार कर सकते हैं।

Answer 3

चूंकि दोनों प्रवेश द्वार और लक्ष्य आइटम सरणी में कहीं भी हो सकते हैं, आपके पास अधिक विकल्प नहीं है, लेकिन सब कुछ खोजने के लिए। इसलिए, आपकी प्रवेश खोज उतनी ही कुशल है जितनी हो सकती है, और लक्षित वस्तुओं के बारे में मैं maze flood fill algorithm की अनुशंसा करता हूं।

हालांकि, एल्गोरिदम का लिंक संस्करण एक दिशा का अनुकूलन करता है (जैसे यह इसे पानी से भर रहा है, यह बाढ़ "नीचे") है। के रूप में यह कर सकते हैं कुशल होने के लिए, आप इसे सभी दिशाओं में विस्तार (जैसे आप यह गैस के साथ भरने कर रहे हैं) बनाना चाहिए, उदा .:

  2 
     1 212 
0 101 21012 
     1 212 
      2 

संख्या विस्तार की पुनरावृत्तियों प्रतिनिधित्व करते हैं। विस्तार चार दिशाओं में किया गया है: बाएं, दाएं, ऊपर और नीचे। जब आप लक्ष्य वस्तु तक पहुंचते हैं, तो आप आसन्न सेल पड़ोसी को बैकट्रैक करके सबसे छोटा रास्ता पा सकते हैं, जिसका पुनरावृत्ति सूचकांक एक से कम होता है, जब तक कि आप 0 पुनरावृत्ति सूचकांक - प्रवेश द्वार पर वापस न आएं।