74分,超时求调,总是TLE
查看原帖
74分,超时求调,总是TLE
1360794
jinjideqingyin楼主2025/7/29 22:59
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> matrix(4, vector<int>(4, 0));
vector<int> row_sums(4), col_sums(4);
int diag_sum, anti_diag_sum;
bool found = false;

void printMatrix() {
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            cout << matrix[i][j];
            if (j < 3) cout << " ";
        }
        cout << endl;
    }
}

bool checkConstraints() {
    // Check row sums
    for (int i = 0; i < 4; ++i) {
        int sum = 0;
        for (int j = 0; j < 4; ++j) {
            sum += matrix[i][j];
        }
        if (sum != row_sums[i]) return false;
    }
    // Check column sums
    for (int j = 0; j < 4; ++j) {
        int sum = 0;
        for (int i = 0; i < 4; ++i) {
            sum += matrix[i][j];
        }
        if (sum != col_sums[j]) return false;
    }
    // Check main diagonal
    int sum = 0;
    for (int i = 0; i < 4; ++i) {
        sum += matrix[i][i];
    }
    if (sum != diag_sum) return false;
    // Check anti-diagonal
    sum = 0;
    for (int i = 0; i < 4; ++i) {
        sum += matrix[i][3 - i];
    }
    if (sum != anti_diag_sum) return false;
    return true;
}

bool canPlace(int i, int j, int val) {
    // Check row sum
    int row_total = 0;
    int unknown = 0;
    for (int k = 0; k < 4; ++k) {
        if (matrix[i][k] == 0 && k != j) unknown++;
        row_total += matrix[i][k];
    }
    if (row_total + val > row_sums[i]) return false;
    if (unknown == 0 && row_total + val != row_sums[i]) return false;
    // Check column sum
    int col_total = 0;
    unknown = 0;
    for (int k = 0; k < 4; ++k) {
        if (matrix[k][j] == 0 && k != i) unknown++;
        col_total += matrix[k][j];
    }
    if (col_total + val > col_sums[j]) return false;
    if (unknown == 0 && col_total + val != col_sums[j]) return false;
    // Check main diagonal
    if (i == j) {
        int diag_total = 0;
        unknown = 0;
        for (int k = 0; k < 4; ++k) {
            if (matrix[k][k] == 0 && k != i) unknown++;
            diag_total += matrix[k][k];
        }
        if (diag_total + val > diag_sum) return false;
        if (unknown == 0 && diag_total + val != diag_sum) return false;
    }
    // Check anti-diagonal
    if (i + j == 3) {
        int anti_diag_total = 0;
        unknown = 0;
        for (int k = 0; k < 4; ++k) {
            if (matrix[k][3 - k] == 0 && k != i) unknown++;
            anti_diag_total += matrix[k][3 - k];
        }
        if (anti_diag_total + val > anti_diag_sum) return false;
        if (unknown == 0 && anti_diag_total + val != anti_diag_sum) return false;
    }
    return true;
}

void solve() {
    if (found) return;
    // Try to fill cells with only one possibility first
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (matrix[i][j] == 0) {
                // Count unknowns in row and column
                int row_unknown = 0, col_unknown = 0;
                for (int k = 0; k < 4; ++k) {
                    if (matrix[i][k] == 0) row_unknown++;
                    if (matrix[k][j] == 0) col_unknown++;
                }
                if (row_unknown == 1 || col_unknown == 1) {
                    // Determine possible value
                    if (row_unknown == 1) {
                        int sum = row_sums[i];
                        for (int k = 0; k < 4; ++k) {
                            sum -= matrix[i][k];
                        }
                        if (sum <= 0 || sum > 300) return;
                        if (canPlace(i, j, sum)) {
                            matrix[i][j] = sum;
                            solve();
                            if (found) return;
                            matrix[i][j] = 0;
                        }
                        return;
                    }
                    if (col_unknown == 1) {
                        int sum = col_sums[j];
                        for (int k = 0; k < 4; ++k) {
                            sum -= matrix[k][j];
                        }
                        if (sum <= 0 || sum > 300) return;
                        if (canPlace(i, j, sum)) {
                            matrix[i][j] = sum;
                            solve();
                            if (found) return;
                            matrix[i][j] = 0;
                        }
                        return;
                    }
                }
            }
        }
    }
    // If no cell with one possibility, proceed with backtracking
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (matrix[i][j] == 0) {
                for (int val = 1; val <= 300; ++val) {
                    if (canPlace(i, j, val)) {
                        matrix[i][j] = val;
                        solve();
                        if (found) return;
                        matrix[i][j] = 0;
                    }
                }
                return;
            }
        }
    }
    // All cells filled, check constraints
    if (checkConstraints()) {
        printMatrix();
        found = true;
    }
}

int main() {
    // Read input
    cin >> row_sums[0] >> row_sums[1] >> row_sums[2] >> row_sums[3];
    cin >> col_sums[0] >> col_sums[1] >> col_sums[2] >> col_sums[3];
    cin >> diag_sum >> anti_diag_sum;
    for (int k = 0; k < 4; ++k) {
        int i, j, val;
        cin >> i >> j >> val;
        matrix[i][j] = val;
    }
    // Solve
    solve();
    return 0;
}
2025/7/29 22:59
加载中...