[問題] [ACM]10349一直WA
我知道這一題似乎是要用bipartite matching
不過我真的搞不懂這東西
所以我嘗試用其他的解法
我的想法是從最左上開始
從左到右從上到下針對幾個case進行處理
如果發現2X2方格的*就直接規劃成2個antenna
如果發現某個*單獨存在(也就是上下左右都沒有其他*)
就規劃作1個antenna
如果發現有個*只在某個方向與另一個*連接
就把這兩個規劃成同一個antenna
當發現*與兩個以上的*相鄰時則暫時不處理
以上規劃過的*全部都會在陣列中被改為o
同時某個變數會檢查陣列是否更動過(也就是這一次搜索是否進行過規劃)
如果沒有會檢查目前的點是否位在相當於右下角的位置
所謂的右下就是右邊及下面是o或超過陣列
是的話就直接讓他和他左邊或上面(如果存在)的*相連
可以說是試著模擬人類解這個問題時的行為
程式會一直進行到某次迴圈後陣列沒有經過任何改變
複雜度是O(N^2)N為陣列大小
我知道toolkit
我想出來的幾個test case送上去結果也和我的output相同
但是送上uva卻是WA
我想問我的想法有什麼遺漏嗎?
另外我在抓input的陣列時是當成字串而不是字元處理
這會影響我的judge的結果嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.69.80
→
04/05 00:32, , 1F
04/05 00:32, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：