hiho 1268 九宮 搜尋 模拟

題目

題目連結：http://hihocoder.com/problemset/problem/1268

題目來源：hiho上的比賽

簡要題意：給定 3×3 矩陣，一些空缺，問是否能構成唯一幻方。

題解

題意比較明白，然後問題比較基礎。

幻方的定義就是橫縱，對角線和都相等，由于和為 45 是以每條都是 15 。

一共 9 個格子，然後每個格子去放入剩下的數字。

枚舉的次數是9!每次就是去做和然後判斷。

枚舉的過程可以利用dfs回溯來做，代碼量較長，适合練手。

為了給某同學看做了注釋。

代碼

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
// head
// 給定的數組
int a[][];
// 臨時使用的數組
int temp[][];
// 數字通路的情況
bool vis[];
// 可以放入數字的位置
vector<PII> b;
// b每個位置上放的數
int path[];
// 輸出的結果
int res[];

// 存在解
bool ok = false;
// 有多個解
bool many = false;

bool judge() {
    // 把目前的數放到臨時的數組裡
    for (int i = ; i < b.size(); i++) {
        temp[b[i].fi][b[i].se] = path[i];
    }
    // 判斷橫和縱的和是否為15
    for (int i = ; i < ; i++) {
        int sumc = , sumr = ;
        for (int j = ; j < ; j++) {
            sumc += temp[i][j];
            sumr += temp[j][i];
        }
        if (sumr !=  || sumc != ) return false;
    }
    // 判斷對角線是否為15
    int sum1 = , sum2 = ;
    for (int i = ; i < ; i++) {
        sum1 += temp[i][i];
        sum2 += temp[-i][i];
    }
    return sum1 ==  && sum2 == ;
}

void dfs(int pos) {
    // 全部放完了開始檢查
    if (pos == b.size()) {
        bool ans = judge();
        // 不合法就結束
        if (!ans) return;
        // 合法根據ok的情況去進行更新
        if (ok) {
            many = true;
        } else {
            ok = true;
            memcpy(res, path, sizeof res);
        }
        return;
    }

    for (int i = ; i <=  && !many; i++) {
        // 用過的數字不用
        if (vis[i]) continue;
        // 更新放的數還有數使用的情況
        path[pos] = i;
        vis[i] = true;
        dfs(pos+);
        // 結束，進行下次
        vis[i] = false;
    }
}

int main() {
    for (int i = ; i < ; i++) {
        for (int j = ; j < ; j++) {
            scanf("%d", a[i]+j);
            // 為0就是可以放數字的，否則就更新使用情況
            if (!a[i][j]) {
                b.push_back(make_pair(i, j));
            } else {
                vis[a[i][j]] = true;
            }
        }

    }
    memcpy(temp, a, sizeof temp);
    dfs();
    // 根據情況輸出
    if (many) {
        puts("Too Many");
    } else if (ok) {
        for (int i = ; i < b.size(); i++) {
            a[b[i].fi][b[i].se] = res[i];
        }
        for (int i = ; i < ; i++) {
            for (int j = ; j < ; j++) {
                printf("%d%c", a[i][j], j== ? '\n' : ' ');
            }
        }
    }
    return ;
}