Codeforces Round #369 (Div. 2) B. Chris and Magic Square 数学、幻方

Source

Codeforces Round #369 (Div. 2)

My Solution

数学、幻方

读入的时候记录好缺口的坐标 x, y

优先判断每行都相等， 然后求出 ans缺口的值

如果 ans <= 0 则无解， 否者就填上去                         //!Wrong answer on pretest 7 的原因

然后判断每列， 以及2条大的对角线

复杂度 O(n^2)

#include 
#include 

using namespace std;
typedef long long LL;
const int maxn = 1e3 + 8;

LL val[maxn][maxn];

int main()
{
    #ifdef LOCAL
    freopen("b.txt", "r", stdin);
    //freopen("o.txt", "w", stdout);
    int T = 5;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, x, y;
    bool flag = true;
    cin >> n;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){ cin >> val[i][j];
            if(val[i][j] == 0){
                x = i; //cout<<x<<endl;
                y = j;
            }
        }
    }

    if(n == 1){
        cout<<1<<endl;
        return 0;
    }

    LL tsum = 0, sum = 0;
    for(int i = 1; i <= n; i++){
        if(i == x) continue;
        sum = 0;
        for(int  j = 1; j <= n; j++){
            sum += val[i][j];
        }
        if(x == 1){
            if(i != 2){
                if(sum != tsum){
                    flag = false;
                    //cout<<i<<endl;
                    break;
                }
            }
            else{
                tsum = sum;
            }
        }
        else{
            if(i != 1){
                if(sum != tsum){
                    flag = false;
                    break;
                }
            }
            else{
                tsum = sum;
            }
        }

        //if(!flag) break;
    }
    if(!flag) cout<<-1<<endl;
    else{
        sum = 0;
        for(int i = 1; i <= n; i++){
            sum += val[x][i];
        }
        val[x][y] = tsum - sum;
        if(val[x][y] <= 0){
            cout<<-1<<endl;
            return 0;
        }


        for(int j = 1; j <= n; j++){
            sum = 0;
            for(int i = 1; i <= n; i++){
                sum += val[i][j];
            }
            if(sum != tsum){
                flag = false;
                break;
            }
        }
        sum = 0;
        for(int i = 1; i <= n; i++){
            sum += val[i][i];
        }
        if(sum != tsum){
            flag = false;
        }

        sum = 0;
        for(int i = 1; i <= n; i++){
            sum += val[i][n - i + 1];
        }
        if(sum != tsum){
            flag = false;
        }

        if(flag) cout<< val[x][y]<<endl;
        else cout<<-1<<endl;



    }



    #ifdef LOCAL
    cout<<endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx