Submission #24453782

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>l_l;

typedef unsigned long long ull;
ull red;
set<ull>used;//調査済みの盤面
vector<string>s;
ll answer=0;
ll n;
vector<ll> dx={1,0,-1,0};
vector<ll> dy={0,1,0,-1};

bool valid(ll x,ll y){
    return 0<=x && x<=n-1 && 0<=y && y<=n-1;//(x,y)が盤面内に含まれているかどうか
}
void change(l_l P){
    //(P.first, P.second)が白マスなら赤マスに、赤マスなら白マスに塗り替える
    ll num=P.first*n+P.second;
    if(s[P.first][P.second]=='@'){
        red-=ull(1)<<num;
        s[P.first][P.second]='.';
    }else{
        red+=ull(1)<<num;
        s[P.first][P.second]='@';
    }
}

void dfs(ll num){
    //num：あと何個赤マスを置くか
    
    if(used.find(red)!=used.end()){
        return;//既に調査済みなので、探索せずに終了する
    }
    used.insert(red);//調査済みの盤面に、現在の盤面を加える

    if(num==0){
        answer++;//現在の盤面は条件を満たす塗り方なので、answerに1加える
        return;  //終了する
    }
    
    vector<l_l>next;//次に赤マスを塗る場所の候補
    
    for(int i=0;i<=n-1;i++){
        for(int j=0;j<=n-1;j++){
            //(i,j)を次の赤マスにできる条件は、
            //s[i][j]が白マス('.')であり、かつ、s[i][j]の隣に赤マス('@')があること
            
            if(s[i][j]=='.'){
                bool flag=false;
                for(int z=0;z<=3;z++){
                    ll nxt_i=i+dx[z];
                    ll nxt_j=j+dy[z];
                    if(valid(nxt_i,nxt_j) && s[nxt_i][nxt_j]=='@'){
                        flag=true;//(i,j)の隣に赤マスがあれば、flagをtrueにする
                    }
                }
                if(flag){
                    next.push_back({i,j});//次に赤マスを塗る場所の候補に、(i,j)を追加する
                }
            }
        }
    }
    for(l_l pos:next){
        change(pos);//赤く塗る
        dfs(num-1); //dfsを進める
        change(pos);//元に戻す
    }
}

signed main(){
    
    ll k;cin>>n>>k;
    s.resize(n);
    for(int i=0;i<=n-1;i++)cin>>s[i];
    
    for(int i=0;i<=n-1;i++){
        for(int j=0;j<=n-1;j++){
            //最初に赤く塗るマスを(i,j)とする
            if(s[i][j]=='.'){
                change({i,j});//赤く塗る
                dfs(k-1);     //dfsを始める
                change({i,j});//元に戻す
            }
        }
    }
    cout<<answer<<endl;
    return 0;
}

Submission Info

Judge Result