[問題] 填色問題

看板Prob_Solve作者 (冷雨)時間14年前 (2009/09/17 23:38), 編輯推噓3(3推 0噓 8→)
留言11則, 3人參與, 最新討論串1/2 (看更多)
※ [本文轉錄自 puzzle 看板] 作者: raincole (冷雨) 看板: puzzle 標題: [問題] 填色問題 時間: Wed Sep 16 07:36:52 2009 有一張6*4的方格紙，將其中12格塗黑，使每列皆有2格、每行皆有3格為黑。 問有多少種上色方法？ 原方格紙： □□□□ □□□□ □□□□ □□□□ □□□□ □□□□ 其中一種上色方法： ■■□□ □■■□ □□■■ ■■□□ ■□□■ □□■■ 這題有沒有什麼方法可以計算？ 又，如果每列要求的黑格數是不等的呢？（每行仍然相等） 版友rehearttw提出交換法， 但假設我一開始的盤面是這樣： □■■□ □■■□ □■■□ ■□□■ ■□□■ ■□□■ 交換以後就會產生重複解了... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 113.61.199.94
推
09/16 09:24,
先找一解，然後橫的交換乘上直的交換，注意一樣的
09/16 09:24
推
09/16 09:54,
老師, 並非所有解之間都可以經由交換變過去的說
09/16 09:54
→
09/16 10:40,
我一開始也是那想法，但那樣會多很多重複解...？
09/16 10:40
→
09/16 10:42,
而且有一些交換會產生不合法解吧...
09/16 10:42
推
09/16 12:01,
舉例錯了? 每行四個圖黑?
09/16 12:01
→
09/16 12:04,
題目每行四個塗黑???
09/16 12:04
→
09/16 12:20,
三格 打題目時疏忽抱歉，謝謝提醒
09/16 12:20
※ 編輯: raincole 來自: 113.61.199.94 (09/16 12:21) ※ 編輯: raincole 來自: 113.61.199.94 (09/16 12:22)
推
09/16 15:03,
例如我把第一橫列和第五橫列交換，不是答案嗎？
09/16 15:03
→
09/16 15:03,
我把第二直行和第三直行交換，不是答案嗎？
09/16 15:03
→
09/16 15:04,
橫的單獨有幾種換法，直的單獨有幾轉換法...
09/16 15:04
→
09/16 15:04,
這應該是高中的不盡相異物排列，只是我不知道是否就是
09/16 15:04
→
09/16 15:04,
全部的答案...
09/16 15:04
→
09/16 15:05,
每列要求的黑格數是不等的，我還沒想出來...
09/16 15:05
→
09/16 15:18,
呃...應該不會產生不合法解沒錯，但重複解呢？
09/16 15:18
※ 編輯: raincole 來自: 113.61.199.94 (09/16 15:19) ※ 編輯: raincole 來自: 113.61.199.94 (09/16 15:19)
推
09/16 15:40,
我的意思就是, 靠交換無法配出所有的解
09/16 15:40
推
09/16 21:57,
能不能證明呢？
09/16 21:57
推
09/16 22:00,
照我的算法，原題目有 4320 種答案。不知答案是？
09/16 22:00
推
09/16 22:05,
嗯！原 PO 後來加的例子，是不能由原解交換得來
09/16 22:05
→
09/16 22:05,
但後來的例子，交換可以得到很多答案
09/16 22:05
推
09/17 05:57,
還想不出好算的方法耶～0.0
09/17 05:57
-- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 113.61.199.94
推
09/18 00:34, , 1F
試試Ploya
09/18 00:34, 1F
→
09/18 00:34, , 2F
polya
09/18 00:34, 2F
→
09/18 00:39, , 3F
應該是這個 http://ppt.cc/9~38
09/18 00:39, 3F
→
09/18 00:42, , 4F
呃...|| 沒事，我好像看錯題意了..
09/18 00:42, 4F
推
09/19 13:43, , 5F
DP 遞迴???左行往右行發展
09/19 13:43, 5F
※ 編輯: raincole 來自: 113.61.199.94 (09/19 16:58)
→
09/19 16:58, , 6F
不懂 怎麼弄？他每行並非只跟上一行有關係吧...
09/19 16:58, 6F
→
09/19 16:58, , 7F
我有想過一個DP解 但維度要和每行黑格數相同...
09/19 16:58, 7F
→
09/19 16:59, , 8F
無法直接開陣列使用，只能拿排序樹存狀態
09/19 16:59, 8F
→
09/19 17:02, , 9F
但應該有更好的解法
09/19 17:02, 9F
推
09/19 21:43, , 10F
rain你說的dp，是像這樣? dp[6][4][4][4][4] ?
09/19 21:43, 10F
→
09/21 01:28, , 11F
對，我看到維數那麼多就高估了空間需求，其實是放的下XD
09/21 01:28, 11F
‣ 更多 raincole 的文章
文章代碼(AID): #1AibWCE1 (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 raincole 的文章
文章代碼(AID): #1AibWCE1 (Prob_Solve)