Mô tả bài toán

Đèn rất kỳ lạ (fan) và đặc biệt (ren), mỗi khi bạn nhấn vào nó, trạng thái của đèn đó và bốn đèn xung quanh sẽ được chuyển đổi (từ mở sang đóng hoặc từ đóng sang mở). Nhiệm vụ của bạn là giúp pmshz bật tất cả các đèn.

Ví dụ:

0  1  1
1  0  0
1  0  1

Khi bạn nhấn vào đèn ở vị trí trung tâm (2,2), trạng thái của nó và các đèn xung quanh sẽ thay đổi thành:

0  0  1
0  1  1
1  1  1

Tiếp tục nhấn vào đèn ở góc trên bên trái (1,1), tất cả các đèn sẽ được bật:

1  1  1
1  1  1
1  1  1

Tất cả các đèn đều đã được bật sau ít nhất 2 lần nhấn.

Đầu vào

Dữ liệu đầu vào gồm 9 số nguyên, được sắp xếp thành một ma trận 3x3, với mỗi cặp số cách nhau bằng một khoảng trắng. Mỗi số đại diện cho trạng thái ban đầu của đèn (0 cho tắt, 1 cho mở).

Đầu ra

Một số nguyên, thể hiện số bước ít nhất cần thiết để tất cả các đèn đều được bật.

Ví dụ đầu vào và đầu ra:

Đầu vào #1:

0 1 1
1 0 0
1 0 1

Đầu ra #1:

2

Giải thích

Đây có lẽ là một bài toán dễ dàng nếu bạn biết cách tiếp cận đúng cách...

#include <iostream>
using namespace std;

const int DIR[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};

// Trạng thái ban đầu của đèn
int grid[3][3];
// Biến lưu trữ số bước ít nhất cần thiết
int minSteps = 10;

// Hàm chuyển đổi trạng thái của đèn tại vị trí (x,y) và các đèn xung quanh
void toggleLight(int tempGrid[3][3], int x, int y) {
    // Chuyển đổi trạng thái của đèn tại vị trí (x,y)
    tempGrid[x][y] = 1 - tempGrid[x][y];

    // Chuyển đổi trạng thái của các đèn xung quanh
    for (int d = 0; d < 4; d++) {
        int newX = x + DIR[d][0];
        int newY = y + DIR[d][1];
        if (newX >= 0 && newX < 3 && newY >= 0 && newY < 3) {
            tempGrid[newX][newY] = 1 - tempGrid[newX][newY];
        }
    }
}

// Kiểm tra xem tất cả các đèn có đều được bật không
bool allLightsOn(int tempGrid[3][3]) {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            if (tempGrid[i][j] == 0)
                return false;
    return true;
}

// Sử dụng thuật toán duyệt sâu (DFS):
// now: Vị trí đèn đang xử lý (0 đến 8)
// steps: Số bước đã thực hiện
// currentGrid: Trạng thái hiện tại của lưới đèn
void dfs(int now, int steps, int currentGrid[3][3]) {
    // Nếu số bước vượt quá giá trị tối ưu hiện tại, cắt tỉa và không tiếp tục tìm kiếm
    if (steps >= minSteps) return;

    // Nếu tất cả các đèn đều đã được xử lý
    if (now == 9) {
        if (allLightsOn(currentGrid)) {
            minSteps = steps;
        }
        return;
    }

    // Tính tọa độ của đèn hiện tại
    int row = now / 3;
    int col = now % 3;

    // ======================
    // Nhánh 1: Không nhấn đèn này
    // ======================
    dfs(now + 1, steps, currentGrid);

    // ======================
    // Nhánh 2: Nhấn đèn này
    // ======================
    toggleLight(currentGrid, row, col);
    dfs(now + 1, steps + 1, currentGrid);
    toggleLight(currentGrid, row, col); // Quay lại trạng thái ban đầu để phục hồi
}

int main() {
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cin >> grid[i][j];

    dfs(0, 0, grid);
    cout << minSteps << endl;
    return 0;
}

• Cách biến đổi tọa độ hiệu quả
• Mỗi đèn chỉ có hai trạng thái (nhấn hoặc không nhấn), nhấn hai lần sẽ trở về trạng thái ban đầu, lãng phí bước đi
• Trong hàm dfs, hai cuộc gọi đệ quy lần lượt đại diện cho việc nhấn và không nhấn đèn hiện tại