TopCoder SRM 148 DIV 1 Medium 練習

問題

縦横の和が全て等しい3*3魔方陣を作る。

魔方陣の要素となる9つの整数が与えられるので、作ることのできる魔方陣が何通りあるか求めなさい。

解

next_permutationゲー。C#にも欲しいです＞＜

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class MNS {
    Dictionary<int, bool> memo;
    bool[] U;
    int[] S, N;

    public int combos(int[] numbers) {
        memo = new Dictionary<int, bool>();
        U = new bool[9];
        S = new int[9];
        N = numbers;
        srch(0);
        return memo.Count;
    }

    private void srch(int p)
    {
        if (p == 9)
        {
            int key = enc(S);
            if (!memo.ContainsKey(key) && check(S))
                memo[key] = true;
        }

        for (int i = 0; i < 9; ++i)
        {
            if (!U[i])
            {
                U[i] = true;
                S[p] = N[i];
                srch(p + 1);
                U[i] = false;
            }
        }
    }

    private int enc(int[] S)
    {
        int n = 0;
        foreach (int i in S)
            n = n * 10 + i;
        return n;
    }

    private bool check(int[] S)
    {
        int sum = S[0] + S[1] + S[2];

        for (int i = 1; i < 3; ++i)
        {
            int s = 0;
            for (int j = 0; j < 3; ++j)
                s += S[i * 3 + j];
            if (s != sum)
                return false;
        }
        for (int i = 0; i < 3; ++i)
        {
            int s = 0;
            for (int j = 0; j < 3; ++j)
                s += S[j * 3 + i];
            if (s != sum)
                return false;
        }
        return true;
    }
}