Submission #1221440

#TimeUsernameProblemLanguageResultExecution timeMemory
122144012345678Solitaire (JOI16_solitaire)C++20
10 / 100
96 ms1104 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=2e3+5, mod=1e9+7;

ll n, dp[(1<<16)];
char mp[4][nx];
vector<pair<int, int>> v;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=3; i++) for (int j=1; j<=n; j++) cin>>mp[i][j];
    for (int i=1; i<=3; i++) for (int j=1; j<=n; j++) if (mp[i][j]=='x') v.push_back({i, j});
    dp[0]=1;
    for (int msk=1; msk<(1<<v.size()); msk++)
    {
        for (int i=0; i<v.size(); i++)
        {
            if (!(msk&(1<<i))) continue;
            for (int j=0; j<v.size(); j++) if ((j!=i)&&(msk&(1<<j))) mp[v[j].first][v[j].second]='o';
            auto [x, y]=v[i];
            if ((mp[x-1][y]=='o'&&mp[x+1][y]=='o')||(mp[x][y-1]=='o'&&mp[x][y+1]=='o')) dp[msk]=(dp[msk]+dp[msk^(1<<i)])%mod;
            for (int j=0; j<v.size(); j++) if (j!=i&&(msk&(1<<j))) mp[v[j].first][v[j].second]='x';
        }
    }
    cout<<dp[(1<<v.size())-1];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...