PE-魔術三角形

2022.11.07 PM 05:00 by CBJ

來源 : https://drive.google.com/file/d/1CMnis82zw9hGQHW1pRv3LFXACoUGA90Y/view
出題者 : 108資訊學科能力競賽複賽-彰雲嘉 
標籤 : 枚舉
難易度 : 3
解題想法 : 窮舉6個格子要放的數字即可(有3個已經內定)
//C++ language
//solution link(含註解): https://github.com/CBJ0519/CBJsProgramDiary.com/blob/main/%E8%B3%87%E8%A8%8A%E5%AD%B8%E7%A7%91%E8%83%BD%E5%8A%9B%E7%AB%B6%E8%B3%BD/108%E5%BD%B0%E9%9B%B2%E5%98%89/PE-%E9%AD%94%E8%A1%93%E4%B8%89%E8%A7%92%E5%BD%A2.cpp

/*   0
    8 1
   7   2
  6 5 4 3  */
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
vector<string>ans;
vector<bool>used(10,false);
vector<int>put(9);
int a,b,c;
bool legal(int i){
    return (i!=a && i!=b && i!=c);
}
bool cmp(string x,string y){
    return x<y;
}
void sattle(){
    int line1=put[0]+put[1]+put[2]+put[3];
    int line2=put[3]+put[4]+put[5]+put[6];
    int line3=put[6]+put[7]+put[8]+put[0];

    string cur_ans="";
    for(int i=0;i<=8;i++){
        cur_ans+=(char)(put[i]+'0');
    }

    if(line1==line2 && line2==line3){
        ans.push_back(cur_ans);
    }
    put.erase(put.begin(),put.end());
}
int main(){
    cin>>a>>b>>c;
    used[0]=used[a]=used[b]=used[c]=true;

    for(int i1=1;i1<=9;i1++){
        if(!legal(i1) || used[i1])continue;
        used[i1]=true;

        for(int i2=1;i2<=9;i2++){
            if(!legal(i2) || used[i2])continue;
            used[i2]=true;

            for(int i3=1;i3<=9;i3++){
                if(!legal(i3) || used[i3])continue;
                used[i3]=true;

                for(int i4=1;i4<=9;i4++){
                    if(!legal(i4) || used[i4])continue;
                    used[i4]=true;

                    for(int i5=1;i5<=9;i5++){
                        if(!legal(i5) || used[i5])continue;
                        used[i5]=true;

                        for(int i6=1;i6<=9;i6++){
                            if(!legal(i6) || used[i6])continue;

                            put[0]=i1; put[1]=a; put[2]=i2; put[3]=i3;
                            put[4]=b; put[5]=i4; put[6]=i5; put[7]=c; put[8]=i6;

                            sattle();

                        }

                        used[i5]=false;
                    }

                    used[i4]=false;
                }

                used[i3]=false;
            }

            used[i2]=false;
        }

        used[i1]=false;
    }

    if(ans.size()==1){
        cout<<ans[0]<<"\n";
    }
    else{
        sort(ans.begin(),ans.end(),cmp);
        cout<<ans[0]<<"\n";
    }
    return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *