C++ 台中區 106-6 馬步問題

參考資料：學科能力複試筆記 – HackMD

微量優化(O(nlog(n)8n) -> O(n8n))。

#include<iostream>
using namespace std;

const int dr[8]={-2,-2,-1,-1,1,1,2,2};
const int dc[8]={-1,1,-2,2,-2,2,-1,1};
int tb[3][20]={0},n,ct=1,sct,ans[3][20];
struct position{
    int r,c;
};

void dfs(position pNow){
    for(int i=0;i<8;i++){
        position pNext={pNow.r+dr[i],pNow.c+dc[i]};
        if(pNext.r>=0 && pNext.c>=0 && pNext.r<3 && pNext.c<n &&
          tb[pNext.r][pNext.c]==0){
            if(ct<3*n-1){
                ct++;
                tb[pNext.r][pNext.c]=ct;
                dfs(pNext);
                ct--;
                tb[pNext.r][pNext.c]=0;
            }else{
                ct++;
                tb[pNext.r][pNext.c]=ct;
                sct++;
                bool lesser=false;
                for(int i=0;i<3;i++){
                    int j;
                    for(j=0;j<n;j++){
                        if(ans[i][j]!=tb[i][j]){
                            lesser=ans[i][j]>tb[i][j];
                            break;
                        }
                    }
                    if(ans[i][j]!=tb[i][j]){
                        break;
                    }
                }
                if(lesser) for(int i=0;i<3;i++){
                    for(int j=0;j<n;j++){
                        ans[i][j]=tb[i][j];
                    }
                }
                ct--;
                tb[pNext.r][pNext.c]=0;
            }
        }
    }
}

int main(){
    cin>>n;
    for(int i=0;i<3;i++){
        for(int j=0;j<n;j++){
            ans[i][j]=10000;
        }
    }
    tb[0][0]=ct;
    position pos={0,0};
    dfs(pos);

    if(sct==0) cout<<"0";
    else for(int i=0;i<3;i++){
        for(int j=0;j<n;j++){
            cout<<ans[i][j]<<" ";
        }
    }
    cout<<"\n";
    return 0;
}