如何查找二維數組（矩形矩陣）是否有直線

Question

我在解決算法問題時偶然發現了這個問題。有一個矩形矩陣。

我找一雙位置作爲輸入，然後我怎麼能計算，如果他們在一條直線下降，對如。在這種情況下，我得到輸入爲（d，B）（c，D）（b，F）（a，H），其實際上是直線。 如果我們仔細看看，短側的計數器跳過1，長邊的計數器跳過2.如果我根據這個邏輯編寫我的代碼，那麼對於更大的矩形是否是一個安全的假設，或者我可以面對這個邏輯問題嗎？

我在這裏假設傾斜的直線只能有兩種類型 1）如果兩個計數器都跳過1，就像方陣的對角線一樣。 2）上面討論的情況，計數器在短邊上跳1，在長邊上跳2。

可以有一組點可以直線排列，但不符合上述任何一個條件，也不能包含在單行或單列中？

Answer 1

好了，讓我們開始從兩個退化情況：

• 如果你有分，回答你的願望（無論是有一條線，或有沒有這樣的線）
• 如果您有或2個點，答案永遠是是

假設，你有3+點，你想檢查它們是否都在同一行。以兩個任意點(x1, y1)和(x2, y2)。再次有兩種情況：

• x1 == x2;檢查所有點是否如此xi == x1

• x1 != x2;檢查所有的點是這樣的：兩個條件滿足：

   (y1 - y2) * (xi - x2) == (yi - y2) * (x1 - x2) 
  (y2*x1 - y1*x2) * (xi - x2) == (y2*xi - yi*x2) * (x1 - x2) 
  

即所有的點都在同y = kx + b行，其中k和b從(x1, y1)和(x2, y2)

得出在你的情況下，當A = 1, B = 2, ..., H = 8; a = 1, b = 2, ..., d = 4我們

(2, 4) 
    (4, 3) 
    (6, 2) 
    (8, 1) 

點，這是在同一條線上。可能的（C＃）實現：

private static bool SameLine(IEnumerable<Tuple<int, int>> points) { 
    if (null == points) 
    return true; 

    Tuple<int, int>[] data = points.ToArray(); 

    // i = 2 - first two points are always on the same line 
    for (int i = 2; i < data.Length; ++i) { 
    int x1 = data[0].Item1; 
    int y1 = data[0].Item2; 

    int x2 = data[1].Item1; 
    int y2 = data[1].Item2; 

    int xi = data[i].Item1; 
    int yi = data[i].Item2; 

    // y = k * x + b where k = infinity 
    if (x1 == x2) { 
     if (xi != x1) 
     return false; 

     continue; 
    } 

    // Same k in y = k * x + b 
    if (!((y1 - y2) * (xi - x2) == (yi - y2) * (x1 - x2))) 
     return false; 

    // Same b in y = k * x + b 
    if (!((y2 * x1 - y1 * x2) * (xi - x2) == (y2 * xi - yi * x2) * (x1 - x2))) 
     return false; 
    } 

    return true; 
} 

測試

Tuple<int, int>[] test = new Tuple<int, int>[] { 
    new Tuple<int, int>(2, 4), 
    new Tuple<int, int>(4, 3), 
    new Tuple<int, int>(6, 2), 
    new Tuple<int, int>(8, 1), 
    }; 

    // Same line 
    Console.Write(SameLine(test) ? "Same line" : "different lines");