→ bleed1979:更正所有cicle為circle，唉。 04/05 06:23
→ loveme00835:您累了嗎? 0.0 04/05 06:31
→ firejox:發音比較有可能錯~~~ 04/05 10:55
這題其實暴力也是0.000s（如果是早期）或是0.008s。
給你演算法。
資料結構，變數
int totalCicle = 0;
// step1
while(true) {
int cicle = 0; // 這一輪圈選了幾次
for(int i = 0; i != y; ++i) {
for(int j = 0; j != x; ++j) {
如果只有一種可能圈選兩個*，
就圈選這一個可能，並把兩個*改成隨便別的符號，表示不能再圈選。
++cicle;
++totalCicle;
}
}
// 如果這一輪都不能圈選，跳出迴圈
if(cicle == 0) {
break;
}
}
// step2
for(int i = 0; i != y; ++i) {
for(int j = 0; j != x; ++j) {
如果可以圈選兩個*，就圈選，並標記不能再圈選。
++totalCicle;
}
}
// step3
掃光所有單一的*，++totalCicle;
// step4
輸出totalCicle，end。
Note: step1的部分建議用bit來代表幾種可能，所以在1，2，4，8為成立。
※ 引述《iamnotgm (伽藍之黑)》之銘言：
: 我知道這一題似乎是要用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: 114.25.240.179