搜索矩陣對角線，垂直和水平形成一個點

Question

我正在尋找一個有效的算法，通過對角線，垂直和水平從一個索引給定點N×N方陣迭代。

例如，在一個4x4矩陣，如果[2][1]是給定的指標，算法應通過索引搜索另一個特定元素的存在：

[0][1], [1][1], [3][1], // Vertically 
[2][0], [2][2], [2][3], // Horizontally 
[3][0], [1][2], [0][3], // Diagonally (/) 
[1][0], [3][2]   // Diagonally (\) 

這張圖片將使它更清晰：

注意給定索引（[2][1]）是不包括在搜索。

---

我設法符號UP C++中的工作溶液，其不那麼有效的：從該元件arr[i][j]

int Check(int arr[][100], int i, int j, int q, int n) 
{ 
    for (int k = 0; k < n; k++) 
     if ((arr[i][k] == q && k != j) || (arr[k][j] == q && k != i)) 
      return 1; 
    //vertical n horizontal 

    if ((i - j) >= 0) 
    { 
     for (int l = i - j, m = 0; l < n; l++) 
      if (arr[l][m++] == q && l != i && (m - 1) != j) 
       return 1; 
    } 
    else 
    { 
     for (int l = j - i, m = 0; l < n; l++) 
      if (arr[m++][l] == q && (m - 1) != i&&l != j) 
       return 1; 
    } 
    // Diagonal (\) 

    int l = i, m = j; 
    while (1) 
    { 
     if (l == 0 || m == n - 1) 
      break; 
     l--; 
     m++; 
    } 

    if (l == 0) 
    { 
     while (m >= 0) 
      if (arr[l++][m--] == q && (l - 1) != i && (m + 1) != j) 
       return 1; 
    } 
    else 
    { 
     while (l < n) 
      if (arr[l++][m--] == q && (l - 1) != i && (m + 1) != j) 
       return 1; 
    } 
    // Diagonal(/) 

    return -1; 
} 

Check()搜索矩陣arr對角，垂直和水平座標如果q存在於任一方向中，則返回1 else，-1。

如何有效實施上述措施？

任何代碼（最好在C/C++中）會很好。

Answer 1

您必須簡化循環內操作，排除對當前單元格的過多檢查。在當前單元格之前和之後分開散步。

//horizontal 
for (int k = 0; k < j; k++) 
     if (arr[i][k] == q) 
      return 1; 
for (int k = j+1; k < n; k++) 
     if (arr[i][k] == q) 
      return 1; 

//main diagonal, case of bottom-left triangle 
dij = i-j; 
if (dij>=0) { 
    for (k=0;k<j;k++) 
     if (arr[k+dij][k] == q) 
      return 1; 
    for (k=i+1;k<n;k++) 
     if (arr[k][k-dij] == q) 
      return 1; 
}