Submission #24453788

---

Source Code Expand

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

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

void dfs(ll num){
    if(num==0){
        answer++;
        return;
    }
    
    vector<l_l>next;
    for(int i=0;i<=n-1;i++){
        for(int j=0;j<=n-1;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;
                    }
                }
                if(flag){
                    s[i][j]='@';
                    dfs(num-1);
                    s[i][j]='#';
                    next.push_back({i,j});
                }
            }
        }
    }
    for(l_l pos:next){
        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++){
            if(s[i][j]=='.'){
                s[i][j]='@';
                dfs(k-1);
                s[i][j]='#';
            }
        }
    }
    cout<<answer<<endl;
    return 0;
}

Submission Info

Judge Result