Module: Lặp lại trên tất cả các mẫu con của một mặt nạ nhất định


Problem

5 /7


Eric và bảng đèn LED

Theory Click to read/hide

Nó xảy ra rằng cần phải liệt kê tất cả các chuỗi bit có độ dài nhất định. Hay nói cách khác, lặp lại tất cả các tùy chọn có thể, trong đó đối với mỗi đối tượng, một trong hai trạng thái có thể được chọn.

Trong những tình huống như vậy, có thể thực hiện liệt kê bằng cách sử dụng mặt nạ bit. Ưu điểm của phương pháp này là mã như vậy hoạt động không đệ quy và hoạt động trên các số thay vì tập hợp hoặc tương tự, giúp cải thiện đáng kể hiệu suất.

Mã chung sử dụng bitmasks được đưa ra dưới đây: intn; // số đối tượng (độ dài chuỗi bit) for (int mask = 0; mask < (1 << n); mask++) { // lặp qua tất cả các số từ 0 đến 2^n - 1, trong đó mỗi số tương ứng với một bitmask // mặt nạ số hiện tại là một bitmask, trong đó bit thứ i chỉ định trạng thái của đối tượng thứ i for (int i = 0; i < n; i++) { // lặp lại n bit để biết trạng thái của từng đối tượng if ((1 << i) & mask) { // kiểm tra xem bit thứ i có bằng 1 không // xử lý tùy chọn mà đối tượng thứ i có trạng thái '1' } else { // trường hợp bit thứ i bằng 0 // xử lý tùy chọn đối tượng thứ i của trạng thái '0' } } }
Mã này chạy trong O(2^n * f(n)), trong đó f(n) là thời gian bạn cần để xử lý một lần lặp cụ thể.

Problem

Eric tìm thấy một bảng đèn LED trong nhà để xe cũ của ông mình. Tuy nhiên, ông ngạc nhiên là khi kích hoạt, các đi-ốt không đồng bộ với nhau. Tức là một số bị cháy, một số thì không.
Bản thân bảng hóa ra là không bình thường. Đó là một lưới hình chữ nhật có n hàng và m cột, trong đó mỗi ô chứa một diode. Gần mỗi hàng có một cần gạt chuyển tất cả các điốt trong hàng này (điốt cháy ra ngoài và ngược lại). Mỗi cột có các đòn bẩy giống nhau (tôi sử dụng các điốt trong cột tương ứng).
Eric tự hỏi liệu có thể chuyển các đi-ốt về trạng thái cũ bằng cách đổi đòn bẩy hay không.

Đầu vào:
Dòng đầu tiên chứa 2 số tự nhiên n và m (1 <= n, m <= 7) - lần lượt là số hàng và số cột trên bàn cờ.
Sau đó, có n dòng với m số trên mỗi dòng - trạng thái của các đi-ốt, trong đó 0 nghĩa là đi-ốt tắt và 1 nghĩa là nó đang bật.

Đầu ra:
In ra "CÓ" nếu có thể đưa các điốt về một trạng thái và "KHÔNG" nếu không thể.

Ví dụ:
 
Giải thích:
Trong ví dụ đầu tiên, bạn có thể chuyển đổi tất cả các điốt ở hàng đầu tiên, sau đó chuyển đổi tất cả các điốt ở cột đầu tiên. Sau đó, tất cả các điốt sẽ tắt.
 
Đầu vào Đầu ra
2 2
0 1
10
2 2
0 1
0 0
KHÔNG