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: