Submission #24453774

---

Source Code Expand

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

set<vector<string>>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 dfs(ll num){
    //num：あと何個赤マスを置くか

    if(used.find(s)!=used.end()){
        return;//既に調査済みなので、探索せずに終了する
    }
    used.insert(s);//調査済みの盤面に、現在の盤面を加える

    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){
        s[pos.first][pos.second]='@';//赤く塗る
        dfs(num-1);                  //dfsを進める
        s[pos.first][pos.second]='.';//元に戻す
    }
}

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]=='.'){
                s[i][j]='@';//赤く塗る
                dfs(k-1);   //dfsを始める
                s[i][j]='.';//元に戻す
            }
        }
    }
    cout<<answer<<endl;
    return 0;
}

Submission Info

Judge Result