用邊界條件導航映射到1D的2D陣列

Question

我試圖實現生活的遊戲，重點在於效率，以及模式匹配的功能。模式是閃光燈，滑翔機，十字架等

我有一個世界的一維數組，以及寬度和高度。爲了找到我想要計算Moore鄰域的索引的鄰居，然後檢查它們是否爲散列，如果它們增加了get_neighbours函數的返回變量。南北方似乎有效，但東方和西方不起作用。 NE，SE，SW，NW都基於先前的邏輯（即，在西部向北）。

int get_neighbours(int loc) { 
    int neighbours = 0; 

    int n = mod(loc - grid_width, total); 
    int e = mod(loc + 1, grid_width) + grid_width; 
    int s = mod(loc + grid_width, total); 
    int w = mod(loc - 1, grid_width) + grid_width; 
    int nw = mod(w - grid_width, total); 
    int ne = mod(e - grid_width, total); 
    int se = mod(e + grid_width, total); 
    int sw = mod(w + grid_width, total); 

    //Northwest 
    if (grid[nw] == '#') { 
     neighbours++; 
    } 
    //North 
    if (grid[n] == '#') { 
     neighbours++; 
    } 
    //Northeast 
    if (grid[ne] == '#') { 
     neighbours++; 
    } 
    //East 
    if (grid[e] == '#') { 
     neighbours++; 
    } 
    //Southeast 
    if (grid[se] == '#') { 
     neighbours++; 
    } 
    //South 
    if (grid[s] == '#') { 
     neighbours++; 
    } 
    //Southwest 
    if (grid[sw] == '#') { 
     neighbours++; 
    } 
    //West 
    if (grid[w] == '#') { 
     neighbours++; 
    } 
    return neighbours; 
} 

int mod(int a, int b) { 
    int ret = a % b; 
    if (b < 0) { 
     return mod(-a, -b); 
    } 
    else if (ret < 0) { 
     ret += b; 
    } 
    return ret; 
} 

對於模式匹配，我試圖使用與上面相同的邏輯來構建5x5子數組。這基本上使用「讀頭」。從所提供的位置向東行進，直到它移動了5個空間。然後，它返回到原始位置，向南移動正確的行數，然後再向東移動，直到我們收集了25個索引。

char *get_subarray(int loc) { 
    char *subarray; 
    subarray = malloc(sizeof(char) * 25); 

    int i = 0; 
    int ptr = loc; 

    while (i < 25) { 
     subarray[i] = grid[ptr]; 
     if ((i + 1) % 5 == 0) { 
      //return the read head to the original location, then travel south through the grid once for each of the times we have traversed a row 
      ptr = loc; 
      for (int k = 0; k <= (i/5); k++) { 
       ptr = mod(ptr + grid_width, total); 
      } 
     } else { 
      ptr = mod(ptr + 1, grid_width) + grid_width; 
     } 
     i++; 
    } 
    subarray[i] = '\0'; 
    return subarray; 

} 

至於它這樣做，它建立在世界上的子陣列，那麼我可以strcmp（）的這對字符串的模式。

int cpu_get_crosses() { 
    int crosses = 0; 

    for (int i = 0; i < total; i++) { 
     if (strcmp(get_subarray(i), "  # # # #  ") == 0) { 
      crosses++; 
     } 
    } 
    return crosses; 
} 

作爲參考，7X5網格指數（含邊界）：

34|28 29 30 31 32 33 34|28 
--|--------------------|-- 
6 |0 1 2 3 4 5 6 |0 
13|7 8 9 10 11 12 13|7 
20|14 15 16 17 18 19 20|14 
27|21 22 23 24 25 26 27|21 
34|28 29 30 31 32 33 34|28 
--|--------------------|-- 
6 |0 1 2 3 4 5 6 |0 

我很好奇，可以讓我來計算摩爾附近的指數，同時保留的邊界是什麼邏輯條件，以便我可以正確計算鄰居和子數組（因爲這兩者都使用相同的邏輯）。

編輯：如果任何googlers需要它的子數組函數。

char *get_subarray(int loc) { 
    char *subarray; 
    subarray = malloc(sizeof(char) * 25); //5x5 (=25) subarray 

    int i = 0; 
    int row = loc/grid_width; 
    int ptr = loc; 

    while (i < 25) { 
     subarray[i] = grid[ptr]; 
     if ((i + 1) % 5 == 0) { 
      //return the read head to the original location, then travel south through the grid once for each of the times we have traversed a row 
      ptr = loc; 
      for (int k = 0; k <= (i/5); k++) { 
       ptr = mod(ptr + grid_width, total); 
      } 
      row = ptr/grid_width; 
     } else { 
      ptr = mod(ptr + 1, grid_width) + row * grid_width; 
     } 
     i++; 
    } 
    subarray[i] = '\0'; 
    return subarray; 
} 

Answer 1

你索引你在逐行方式排列：index(i, j) = j * grid_width + i爲i=0..grid_width-1, j=0..grid_height-1。讓我們把loc的index(i, j)結果和反向index得到i和j：

int i = loc % grid_width; 
int j = loc/grid_width; 

往東走加一i，一個往西走下降，兩者模寬度：

int e = j * grid_width + (i + 1) % grid_width 
     = j * grid_width + ((j * grid_width + i) + 1) % grid_width 
     = j * grid_width + (loc + 1) % grid_width; 
int w = j * grid_width + (i + grid_width - 1) % grid_width 
     = j * grid_width + ((j * grid_width + i) + grid_width - 1) % grid_width 
     = j * grid_width + (loc + grid_width - 1) % grid_width; 

備註：

1. (i + grid_width - 1) % grid_width等於mod(i - 1, grid_width)
2. x % M = (k * M + x) % M任何積分k，這讓我們我們loc = j * grid_width + i替換i在任何表達式模grid_width，以避免在第一位置計算i）

通過一個模數的高度等於添加grid_width和增加j由total包裝total是寬x高。使其更明確，這裏的推導：

int j1 = (j + 1) % grid_height; 
int s = j1 * grid_width + i 
     = ((j + 1) % grid_height) * grid_width + i 
     = ((j + 1) * grid_width) % (grid_height * grid_width) + i 
     = ((j + 1) * grid_width) % total + i 
     = (j * grid_width + grid_width + i) % total 
     = ((j * grid_width + i) + grid_width) % total 
     = (loc + grid_width) % total; 
// analogue for j0 = (j + grid_height - 1) % grid_height; 
int n = (loc + total - grid_width) % total;