切換
舊版
前往
大廳
主題

ZeroJudge - b185: 6. 按鈕問題 解題心得

Not In My Back Yard | 2019-09-17 22:33:52 | 巴幣 0 | 人氣 199

題目連結:


題目大意:
給定兩正整數 n 、 m (1 ≦ n 、 m ≦ 6),代表接著有 n 列的輸入,每列有 m 個字元。

每個字元可能是「O」或是「X」兩者之一。前者代表突起(代表尚未壓下)的按鈕,後者代表已壓下的按鈕。當按下一個突起的按鈕後,該按鈕會改變狀態並且也同時改變其相鄰(上下左右)的按鈕狀態。

試問,將所有按鈕都變為壓下的狀態,最少需要按下幾個按鈕?如果不可能達成,請輸出「Can not」。



範例輸入:
2 2
OO
OO
1 2
OX
6 6
XXXXXX
XXXOXX
XXOOOX
XOXOXX
OOOXXX
XOXXXX


範例輸出:
Minimum Steps :4
Can not
Minimum Steps :2


解題思維:
這題的作法類似。也是窮舉第一列的情況並往第二、三列等等根據第一列的狀況按按鈕。(但是要注意只有一列(甚至是只有一個按鈕)的狀況)

再加上,本題的按鈕圖之大小跟該題的 10 × 10 顯得較為彈性(儘管版面較小),所以該題的程式碼需做一些調整才能用於本題。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作