Official

E - Red Polyomino Editorial by sugarrr


\(N^2\) 個のマスから \(K\) 個選ぶ方法は \(_{N^2}C_{K}\) 通りあり、\(_{64}C_{8} =4426165368 \gt 4 \times 10^9\) なので、愚直な全探索は間に合いません。
しかし、赤マス同士が連結という条件から、条件を満たす選び方はそれより相当に少ないことが予想できます。これは、何らかの方法で上から評価してもよいですが、今回は入出力例 \(3\) から見積もることができます。
したがって、赤マス同士が連結という条件を満たすパターンのみ列挙するdfsをすればよいです。
dfsは書き慣れていないと実装が難しいと思うので、下の例も参考にしてください。

#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;
}

なお、上記の実装例は読みやすさを重視していて少し遅いです。
https://atcoder.jp/contests/abc211/submissions/24453774 (541ms)

盤面の情報を vector<string> ではなく64bit整数( unsigned long long など)で管理すると高速化できます。
https://atcoder.jp/contests/abc211/submissions/24453782 (85ms)

少し難しいですが、同じ盤面では \(1\) 度しかdfsに入らないようにする実装もあります。
https://atcoder.jp/contests/abc211/submissions/24453788 (25ms)

posted:
last update: