題意：給你一個正方形棋盤。每個棋子可以直線攻擊，除非隔着石頭。現在要求所有棋子都不互相攻擊，問最多可以放多少個棋子。
這個題可以用搜尋來做。每個棋子考慮放與不放兩種情況，然後再判斷是否能互相攻擊來剪枝。最後取可以放置的最大值。
這裡我轉化成求最大獨立集來做。
首先将每個空地編号，對于每個空地，與該位置可以攻擊到的空地連邊。找最多的空地使得不互相攻擊，即求該圖的最大獨立集。與搜尋做法基本一緻，但是說法略有不同。
view code
題意：給你一個正方形棋盤。每個棋子可以直線攻擊，除非隔着石頭。現在要求所有棋子都不互相攻擊，問最多可以放多少個棋子。
這個題可以用搜尋來做。每個棋子考慮放與不放兩種情況，然後再判斷是否能互相攻擊來剪枝。最後取可以放置的最大值。
這裡我轉化成求最大獨立集來做。
首先将每個空地編号，對于每個空地，與該位置可以攻擊到的空地連邊。找最多的空地使得不互相攻擊，即求該圖的最大獨立集。與搜尋做法基本一緻，但是說法略有不同。
view code