如何從數組中找到模板？

Question

如何在數組中找到模板？ 模板

int[] = {X, X, X}; //(example 3,3,3) 

，或者模板

int[,] temp2 = 
{ 
    {X, X, ?} 
    {?, X, X} 
} 

例

int[,] temp2 = 
{ 
    {3, 3, 1} 
    {2, 3, 3} 
} 

例如，在這樣的陣列？

int[,] a = new int[,] 
{ 
    { 1, 4, 5, 3, 4 }, 
    { 1, 2, 3, 1, 3 }, 
    { 1, 1, 2, 4, 4 }, 
    { 4, 4, 3, 3, 3 }, 
    { 3, 4, 4, 5, 5 } 
}; 

有沒有比搜索每個單元格及其相鄰單元更快的方法？

Answer 1

如果您正在尋找更大陣列中的模式，可能需要逐個檢查單元格纔是唯一的方法。你可以做一些複雜的優化，以跳過?的值並加快一點，但我認爲它不會輕鬆工作。

樣本代碼，應該做你問：

// null means anything is ok, X is 0, Y is 1, Z is 2... 
int?[,] temp = new int?[,] 
{ 
    {0, 0, null}, 
    {null, 0, 0} 
}; 

int[,] a = new int[,] 
{ 
    { 0, 1, 1, 2, 4, 4, 1 }, 
    { 0, 1, 4, 4, 3, 3, 3 }, 
    { 0, 2, 3, 4, 4, 5, 5 } 
}; 

int row, col; 
bool success = CheckPattern(temp, a, out row, out col); 

Console.WriteLine("Success: {0}, row: {1}, col: {2}", success, row, col); 

然後

private static bool CheckPattern(int?[,] temp, int[,] data, out int row, out int col) 
{ 
    int rowsT = temp.GetLength(0); 
    int colsT = temp.GetLength(1); 

    int rowsD = data.GetLength(0); 
    int colsD = data.GetLength(1); 

    // Find the "maximum" value of the template (how many different 
    // condition are there... If there is only "X" then 1, "X", "Y" then 2, 
    // "X", "Y", "Z" then 3... 
    int max = -1; 

    for (int i = 0; i < rowsT; i++) 
    { 
     for (int j = 0; j < rowsT; j++) 
     { 
      if (temp[i, j] != null) 
      { 
       max = Math.Max(temp[i, j].Value, max); 
      } 
     } 
    } 

    // We save in an array the "current" values of "X", "Y", "Z", ... 
    int?[] values = new int?[max + 1]; 

    for (int i = 0; i < rowsD - rowsT + 1; i++) 
    { 
     for (int j = 0; j < colsD - colsT + 1; j++) 
     { 
      Array.Clear(values, 0, values.Length); 

      bool success = true; 

      // Check the template 
      for (int k = 0; k < rowsT; k++) 
      { 
       for (int r = 0; r < colsT; r++) 
       { 
        if (temp[k, r] != null) 
        { 
         int? curr = values[temp[k, r].Value]; 

         if (curr == null) 
         { 
          // If this is the first time we check this 
          // condition, then any value is good 
          values[temp[k, r].Value] = data[i + k, j + r]; 
         } 
         else if (curr.Value == data[i + k, j + r]) 
         { 
          // For subsequent instances we check this 
          // condition, then the data must have the 
          // value found in the previous instance 
         } 
         else 
         { 
          success = false; 
          break; 
         } 
        } 
       } 

       if (!success) 
       { 
        break; 
       } 
      } 

      if (success) 
      { 
       row = i; 
       col = j; 
       return true; 
      } 
     } 
    } 

    row = 0; 
    col = 0; 
    return false; 
} 

這段代碼應該多個條件"X", "Y"...