檢查相鄰網格的最有效的方法

Question

假設我有一個大小爲NxN的二維數組A表示的大方形網格，並且一個點在其座標上被分配給一個網格。每個網格由八個相鄰的網格圍繞（想想鍵盤中的數字鍵盤，5號被1,2,3,4,6,7,8,9包圍）。

現在對於每個相鄰的網格我都會爲它做點什麼，但是數組中的某些元素可能沒有八個相鄰的網格。如果是在其中一個寄宿生中，那麼它只有五個鄰居（如2號只被1,3,4,5,6包圍），並且如果它在四個角落中的一個上，那麼它只被包圍三個鄰居。給定數組A的一個元素，如何以最有效的方式檢查其鄰居？我可以設置許多if語句來查看它的數組索引是大於0還是小於N-1，但是如何組合（嵌套）這些if語句以便需要最少的步數？

感謝

Answer 1

如果你不希望每個元素來檢查，你可以使用一個for循環i=1,j=1; i<N-1 && j<N-1; i++,j++爲「安全」的元素少的條件。

然後使用一個循環遍歷每一行，像這樣j=1;j<N-1;j++ {check array[0][j] and array[N-1][j]和我一樣。

現在，你只需要檢查角落。

以這種方式，沒有元素檢查更多的條件，然後它必須。

Answer 2

pt: (i,j) 
if(i>0 &&j>0&& i<n-1&&j<n-1){ 
//not a border element. 
} 
else{ 
    if(i+j == 0|| i+j == n-1 || i+j == 2(n-1)){ 
    //four corner points ie #neighbour = 3 
    } 
    else{ 
    //boundary points with #neighbour = 5 
    } 
} 

Answer 3

我認爲你將不得不時間不同的方法。這是直接從一個簡單的「生命遊戲」程序中刪除，它計算周圍的白色單元的數量。

無論你如何骰子你最終做出不少的ifs和buts。所以，我在此落戶，相當明顯，做法，即我最初修改的開始和結束變量的循環：

unsigned count_neighbours(const sf::Image& img, unsigned x, unsigned y) 
{ 
    unsigned c = 0; 

    auto Nx = img.getSize().x; 
    auto Ny = img.getSize().y; 

    unsigned xb = x ? x - 1 : x; 
    unsigned yb = y ? y - 1 : y; 
    unsigned xe = (x == Nx - 1) ? Nx : x + 2; 
    unsigned ye = (y == Ny - 1) ? Ny : y + 2; 

    for(auto xi = xb; xi < xe; ++xi) 
     for(auto yi = yb; yi < ye; ++yi) 
      if(xi != x || yi != y) 
       if(img.getPixel(xi, yi) == sf::Color::White) 
        ++c; 
    return c; 
} 

Answer 4

通過@ClsForCookies的解決方案是一個極好的，因爲絕大多數的節點都在內部和將不需要任何測試。

無論如何，這隻有在您可以自由施加訪問訂單並且您接受複製代碼時纔可用。

因此，現在我會假設你不提前知道節點索引。

一種選擇是在網格周圍使用帶有額外餘量的位數組。該位告訴你，如果你不在電網。

另一種方法是使用與原始網格大小相同的代碼數組（或向節點添加屬性）。代碼會告訴你節點的配置（左上角，上邊...）。有九種情況。對於每9個可能的值，您可以預先存儲可能的位移列表到現有的鄰居（3到8種可能性）。

並非存儲的9碼整個陣列，則可以計算它們與式

Code = (0 < i + 2 * (i >= N)) + 3 * (0 < j + 2 * (j >= N)) 

爲了限制存儲你也可以預先存儲在兩個一維陣列中的i和j份的代碼。

最後，您可以使用下面的方案來掃描周圍(i, j)：

if i > 0: 
    i-- 
    if j > 0: 
     j--; Process; j++ 
    Process 
    if j < N-1: 
     j++; Process; j-- 
    i++ 
if j > 0: 
    j--; Process; j++ 
if j < N-1: 
    j++; Process; j-- 
if i < N-1: 
    i++ 
    if j > 0: 
     j--; Process; j++ 
    Process 
    if j < N-1: 
     j++; Process; j-- 
    i-- 

不幸的是，成本是最大的（8個測試）的內部節點。