Submission #660884

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}

int dx[]={-2,0,2,-1,0,1,-2,-1,0,1,2,-1,0,1,-2,0,2};
int dy[]={-2,-2,-2,-1,-1,-1,0,0,0,0,0,1,1,1,2,2,2};


int fld[10][10];
bool ng[10][10];
int dp[10][10];
bool check(){
    memset(dp,0,sizeof(dp));
    memset(ng,0,sizeof(ng));
    rep(i,10)rep(j,10){
        if(!fld[i][j])continue;
        rep(d,17){
            int ny=i+dy[d],nx=j+dx[d];
            if(ny<0||ny>=10||nx<0||nx>=10)continue;
            ng[ny][nx]=true;
        }
    }
    rep(i,10)dp[i][0]=1;
    rep(j,10){
        rep(i,10){
            for(int dy=-1;dy<=1;dy++){
                int ny=i+dy,nx=j-1;
                if(ny<0||ny>=10||nx<0||nx>=10)continue;
                dp[i][j]+=dp[ny][nx];
            }
            if(ng[i][j])dp[i][j]=0;
        }
    }
    int ans=0;
    rep(i,10)ans+=dp[i][9];
    return ans==1;
}

bool ok=false;
void dfs(int y,int x,int n){
    if(y==10){
        if(check()){
            ok=true;
            rep(i,10){
                rep(j,10){
                    if(fld[i][j])cout<<"C";
                    else cout<<".";
                }cout<<endl;
            }
        }
        return;
    }
    if(ok)return;
    int ny=y+(x==9),nx=(x+1)%10;
    if(n!=5){
        fld[y][x]=1;
        dfs(ny,nx,n+1);
        fld[y][x]=0;
    }
    dfs(ny,nx,n);
}

signed main(){
    dfs(0,0,0);
    return 0;
}

Submission Info

Judge Result