文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡書
1. 枚舉
枚舉是基于逐個嘗試答案的一種問題求解策略。
2. 熄燈問題（POJ1222）
-
問題描述
有一個由按鈕組成的矩陣，其中每行有6個按鈕，共5行。每個按鈕的位置上有一盞燈。當(dāng)按下一個按鈕后，該按鈕以及周圍位置(上邊、下邊、左邊、右邊)的燈都會改變一次。
Figure 1
如果燈原來是點亮的，就會被熄滅；如果燈原來是熄滅的，則會被點亮。在矩陣角上的按鈕改變3盞燈的狀態(tài)；在矩陣邊上的按鈕改變4盞燈的狀態(tài)；其他的按鈕改變5盞燈的狀態(tài)。
Figure 2
與一盞燈毗鄰的多個按鈕被按下時，一個操作會抵消另一次操作的結(jié)果。對矩陣中的每盞燈設(shè)置一個初始狀態(tài)。請你按按鈕，直至每一盞等都熄滅。 輸入
5行組成，每一行包括6個數(shù)字（0或1）。相鄰兩個數(shù)字之間用單個空格隔開。0表示燈的初始狀態(tài)是熄滅的，1表示燈的初始狀態(tài)是點亮的。輸出
5行組成，每一行包括6個數(shù)字（0或1）。相鄰兩個數(shù)字之間用單個空格隔開。其中的1表示需要把對應(yīng)的按鈕按下，0則表示不需要按對應(yīng)的按鈕。輸入樣例
0 1 1 0 1 0
1 0 0 1 1 1
0 0 1 0 0 1
1 0 0 1 0 1
0 1 1 1 0 0
- 輸出樣例
1 0 1 0 0 1
1 1 0 1 0 1
0 0 1 0 1 1
1 0 0 1 0 0
0 1 0 0 0 0
分析
假設(shè)當(dāng)前燈亮，按鈕按一次，燈變滅，再按一次，燈又變亮，恢復(fù)到了初始狀態(tài)，因此，按鈕按兩次是沒意義的。結(jié)論：按鈕按偶數(shù)次沒意義，按鈕按奇數(shù)次與按一次一樣，因此，每個按鈕最多按一次。解題思路
- 枚舉所有可能的按鈕狀態(tài)，每種狀態(tài)計算一下最后的情況，看是否都熄滅。所有狀態(tài)數(shù)為$2^30$，因此這種方案不可行。
- 如果存在某個局部，一旦這個局部的狀態(tài)確定，那么剩下的其它狀態(tài)只能是確定的一種，或不多的n種，則只需要枚舉這個局部即可。以第一行為例，假設(shè)它就是那個局部，如果第一行的狀態(tài)確定了，是不是第二行的狀態(tài)就確定了呢？答案是是的，因為第一行按鈕按過之后，亮的燈只有按第二行才能將其熄滅。同理，第二行按鈕按下后，只能通過第三行按鈕來控制燈熄滅。
- 枚舉第一行的所有可能狀態(tài)，每個位置有0和1兩種狀態(tài)，共6個位置，因此第一行的所有可能狀態(tài)為$2^6=64$種，枚舉狀態(tài)可以通過遞歸實現(xiàn)。如果使用每個比特位代表一個燈的話，則可能的狀態(tài)為數(shù)字0-63。
- 方法一
#!/usr/bin/env python
# _*_ coding: utf-8 _*_
import numpy as np
# 枚舉第一行的所有可能狀態(tài)
def all_status(status_list, status, depth):
rows, columns = status.shape
other = status.copy()
other[0, depth] = 1
if depth == columns - 1:
status_list.append(status.copy())
status_list.append(other.copy())
else:
all_status(status_list, status.copy(), depth + 1)
all_status(status_list, other.copy(), depth + 1)
# 如果按鈕按下，更改燈的狀態(tài)
def light_change(input_data, i, j):
rows, columns = input_data.shape
input_data[i, j] = (input_data[i, j] + 1) % 2
if (i - 1) >= 0:
input_data[i - 1, j] = (input_data[i - 1, j] + 1) % 2
if (i + 1) < rows:
input_data[i + 1, j] = (input_data[i + 1, j] + 1) % 2
if (j - 1) >= 0:
input_data[i, j - 1] = (input_data[i, j - 1] + 1) % 2
if (j + 1) < columns:
input_data[i, j + 1] = (input_data[i, j + 1] + 1) % 2
# 嘗試關(guān)閉所有燈
def light_off(input_data, output_data):
rows, columns = input_data.shape
# 根據(jù)第一行按鈕的狀態(tài)修改燈的亮滅
for i in xrange(0, columns):
if output_data[0, i] == 1:
light_change(input_data, 0, i)
# 從第二行開始，每一行的按鈕都使上一行的燈熄滅
for i in xrange(1, rows):
for j in xrange(0, columns):
if input_data[i - 1, j] == 1:
light_change(input_data, i, j)
output_data[i, j] = 1
if np.sum(input_data) == 0:
return True, output_data
else:
return False, output_data
# 輸出指定格式的結(jié)果
def print_result(output_data):
rows, columns = output_data.shape
for i in xrange(rows):
binary_string = ''
for j in xrange(columns):
binary_string += str(output_data[i, j])
print binary_string
input_list = []
input_data = np.array([[0, 1, 1, 0, 1, 0],
[1, 0, 0, 1, 1, 1],
[0, 0, 1, 0, 0, 1],
[1, 0, 0, 1, 0, 1],
[0, 1, 1, 1, 0, 0]], dtype = 'int8')
input_list.append(input_data)
input_data = np.array([[0, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1],
[0, 0, 1, 0, 1, 1],
[1, 0, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 0]], dtype = 'int8')
input_list.append(input_data)
status_list = []
status = np.zeros((5, 6), dtype = 'int8')
all_status(status_list, status, 0)
for i in xrange(len(input_list)):
input_data = input_list[i]
for j in xrange(len(status_list)):
flag, output_data = light_off(input_data.copy(), status_list[j].copy())
if flag:
print j
print 'PUZZLE #%d' % (i + 1)
print_result(output_data)
break
- 結(jié)果
PUZZLE #1
101001
110101
001011
100100
010000
PUZZLE #2
100111
110000
000100
110101
101101
- 方法二
#!/usr/bin/env python
# _*_ coding: utf-8 _*_
# 取特定位置上的比特，索引從0開始
def get_bit(number, index):
return (number >> index) & 1
# 設(shè)定特定位置上的比特
def set_bit(number, index, value):
return number | (value << index)
# 特定位置上的比特反轉(zhuǎn)
def flip(number, index):
return number ^ (1 << index)
# 如果按鈕按下，更改燈的狀態(tài)
def light_change(input_data, i, j):
rows = 5
columns = 6
input_data[i] = flip(input_data[i], j)
if (i - 1) >= 0:
input_data[i - 1] = flip(input_data[i - 1], j)
if (i + 1) < rows:
input_data[i + 1] = flip(input_data[i + 1], j)
if (j - 1) >= 0:
input_data[i] = flip(input_data[i], j - 1)
if (j + 1) < columns:
input_data[i] = flip(input_data[i], j + 1)
# 嘗試關(guān)閉所有燈
def light_off(input_data, output_data):
rows = 5
columns = 6
# 根據(jù)第一行按鈕的狀態(tài)修改燈的亮滅
for i in xrange(0, columns):
if get_bit(output_data[0], i) == 1:
light_change(input_data, 0, i)
# 從第二行開始，每一行的按鈕都使上一行的燈熄滅
for i in xrange(1, rows):
for j in xrange(0, columns):
if get_bit(input_data[i - 1], j) == 1:
light_change(input_data, i, j)
output_data[i] = set_bit(output_data[i], j, 1)
if input_data[-1] == 0:
return True
else:
return False
# 輸出指定格式的結(jié)果
def print_result(output_data):
for i in xrange(len(output_data)):
binary_string = bin(output_data[i])[2:]
diff = 6 - len(binary_string)
for j in xrange(diff):
binary_string = '0' + binary_string
print binary_string
input_list = []
input_data = [int('011010', 2), int('100111', 2), int('001001', 2), int('100101', 2), int('011100', 2)]
input_list.append(input_data)
input_data = [int('001010', 2), int('101011', 2), int('001011', 2), int('101100', 2), int('010100', 2)]
input_list.append(input_data)
for i in xrange(len(input_list)):
input_data = input_list[i]
for j in xrange(64):
copy = [input_data[x] for x in xrange(len(input_data))]
output_data = [0 for k in xrange(5)]
output_data[0] = j
flag = light_off(copy, output_data)
if flag:
print 'PUZZLE #%d' % (i + 1)
print_result(output_data)
break
- 結(jié)果
PUZZLE #1
101001
110101
001011
100100
010000
PUZZLE #2
100111
110000
000100
110101
101101
總結(jié)：這個問題比較復(fù)雜，其中隱含的一點就是局部狀態(tài)確定后，后面的狀態(tài)都會被確定，此時需要枚舉局部狀態(tài)。方法一與方法二的求解思路是一樣，但實現(xiàn)方式不一樣，方法一使用Numpy來處理數(shù)據(jù)，而方法二使用比特來處理數(shù)據(jù)。
源碼地址：Numpy方法，二進制比特方法，記得給個star。
