首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

POJ 1222:Lights Out 變體 - 高斯消元法求解開關矩陣

     編輯:關於C++

問題建模

5×6 矩陣,每格為開關(0/1)。按下開關會翻轉自身及上下左右四鄰格。目標:使所有燈熄滅(全 0)。每個開關至多按一次(多次等價於 0/1)。

線性方程組構建

  • 30 個變量 x_0..x_29 表示是否按下對應開關。
  • 30 個方程:每個燈最終狀態 = 初始狀態 ⊕ 影響它的開關變量和 = 0。
  • 係數矩陣 Map[30][30],常數項 a[30] 為初始狀態。

高斯消元求解(模 2 域)

異或運算代替加減乘除:

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved