算法通過不同單元格內容的模式來匹配網格

Question

我正在尋找一種算法來匹配不同單元格內容的模式上的大小相同的網格，而不是實際的單元格值本身。 網格在單元格上的匹配位置與在另一個網格中相同位置的可能不同值相同的位置具有相同的值。的成功和失敗使用2×2的網格

實例：

成功匹配：
電網A：
[0] [1]
[3] [0]

電網B：
[25] [17]
[23] [25]

非匹配網格：
網格A：
[0] [1]
[3] [0]

電網B：
[25] [17]
[23] [17]

此示例未能匹配爲由於[0]與[3]匹配，b [0]的值與b [3]不匹配。

Answer 1

我假設您所指的圖案形狀意味着在網格中具有相同位置處的相同值，與模式網格中相同位置處的可能不同值相同。

通過用一串字符創建表示網格中的模式的模式字符串，您可以輕鬆解決此問題。爲了創建這個字符串，我們通過網格。當我們發現一個我們以前從未見過的新值時，我們爲該值分配一個新的字符。當我們找到一個我們以前見過的值時，我們使用之前分配給該值的字符。

所以我們得到一個從A到P的字符串（在指定的網格中最多有16個不同的值）。

在你的問題的例子中，兩個網格都會產生字符串「ABCA」。

通過比較爲網格生成的模式字符串，可以輕鬆查看兩個網格是否具有相同的模式。

下面是一個簡單的函數來創建這樣的模式串：

// Calculates a code string representing the pattern in a grid 
// by a string of characters from A to P. 
public static string CalculatePatternSignature(IEnumerable<IEnumerable<int>> grid) 
{ 
    string result = ""; 

    // Here we remember what number represents what letter in the pattern 
    Dictionary<int, char> symbolMap = new Dictionary<int, char>(); 


    // Going row by row and then column by column 
    // we look at each number from top left to bottom right 
    foreach (var row in grid) 
    { 
     foreach(var cell in row) 
     { 
      // For each number we try to map it to a letter from 
      // A to P (16 different values possible) 
      char mappedChar; 

      // We look whether we have seen the integer value before 
      // If yes, we can read its assigned mapped letter from the dictionary 
      if (!symbolMap.TryGetValue(cell, out mappedChar)) 
      { 
       // We haven't seen that integer value before, 
       // so use the next free letter and map the 
       // value to that letter 
       mappedChar = (char)((byte)'A' + symbolMap.Count()); 
       symbolMap.Add(cell, mappedChar); 

       if (symbolMap.Count() > 16) 
       { 
        throw new Exception("We have found more than 16 different values in the grid"); 
       } 
      } 

      // Add the mapped letter for the integer value in the current cell 
      // to the code string 
      result += mappedChar; 
     } 
    } 

    return result; 
} 

示例代碼以證明它們產生的相同的模式串：

var samplePattern = new int[][] { 
    new int[] {0, 1}, 
    new int[] {3, 0} 
}; 

var sampleInput = new int[][] { 
    new int[] {25, 17}, 
    new int[] {23, 25} 
}; 

textBox1.AppendText("samplePattern: " + CalculatePatternSignature(samplePattern) + Environment.NewLine); 
textBox1.AppendText("sampleInput: " + CalculatePatternSignature(sampleInput) + Environment.NewLine); 

產生以下輸出：

samplePattern：ABCA
sampleInput：ABCA