Ideone.com

fork download

copy

#include <iostream>
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
 
char arr[16][16];
int dp[16][1125];
int dp2[1125][1125];
int dp3[1125];
 
int n,m;
 
int cases;
 
int isitok(int a,int nth,int b){
 
    bool okay=true;
 
    if(dp3[a]==1){
        okay=false;
    }
 
    if(dp2[a][b]==1){
        okay=false;
    }
 
    int ret=0;
 
    if(okay){
    int ba=a;
    int ab=b;
 
    char temp[15];
    char temp2[15];
 
    for(int i=0;i<m;i++){
        if(a%2){
            temp[i]='.';
            ret++;
        }
        else{
            temp[i]='x';
        }
        a/=2;
    }
 
 
    for(int i=0;i<m;i++){
        if(temp[i]=='.' && arr[nth][i]=='x'){
            okay=false;
            break;
            //cout<<nth<<ba<<ab<<"는1탈락"<<endl;
        }
    } //앉을 수 있는 자리인지 확인
 
 
 
 
    if(okay){
    for(int i=0;i<m-1;i++){
        if(temp[i]=='.' && temp[i+1]=='.'){
            okay=false;
            dp3[ba]=1;
            break;
            //cout<<nth<<ba<<ab<<"는2탈락"<<endl;
        }
    }//같이 앉았는지 확인
 
    if(okay){
 
    for(int i=0;i<m;i++){
        if(b%2){
            temp2[i]='.';
        }
        else{
            temp2[i]='x';
        }
        b/=2;
    }
 
    if(okay){
 
    for(int i=0;i<m;i++){
        if(i-1>=0 && temp[i]=='.' && temp2[i-1]=='.'){
            okay=false;
            dp2[ba][ab]=1;
            dp2[ab][ba]=1;
            break;
            //cout<<nth<<ba<<ab<<"는3탈락"<<endl;
        }
        if(i+1<n && temp[i]=='.' && temp2[i+1]=='.'){
            okay=false;
            dp2[ba][ab]=1;
            dp2[ab][ba]=1;
            break;
            //cout<<nth<<ba<<ab<<"는4탈락"<<endl;
        }
    }
 
    }
    }
    }
    }
 
    if(okay){
        return ret;
    }
    else{
        return 0;
    }
}
 
int main()
{
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int c;
    cin>>c;
 
    for(int i=0;i<c;i++){
 
        cin>>n>>m;
 
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                arr[i][j]='\0';
            }
        }
 
        cases=1;
        for(int i=0;i<m;i++){
            cases*=2;
        }
 
        for(int i=0;i<n;i++){
            for(int j=0;j<cases;j++){
                dp[i][j]=0;
            }
        }
 
        for(int j=0;j<n;j++){
            cin>>arr[j];
        }
 
        for(int k=0;k<cases;k++){
            dp[0][k]=isitok(k,0,0);
        }
 
 
        for(int i=1;i<n;i++){
            for(int k=0;k<cases;k++){
                for(int j=0;j<cases;j++){
                    dp[i][k]=max(dp[i][k],dp[i-1][j]+isitok(k,i,j));
                }
            }
        }
 
        int maxe=0;
 
        for(int j=0;j<cases;j++){
            maxe=max(maxe,dp[n-1][j]);
        }
 
 
        cout<<maxe<<'\n';
 
    }
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk8zIikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk9mYXN0IikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUoInVucm9sbC1sb29wcyIpCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2hhciBhcnJbMTZdWzE2XTsKaW50IGRwWzE2XVsxMTI1XTsKaW50IGRwMlsxMTI1XVsxMTI1XTsKaW50IGRwM1sxMTI1XTsKCmludCBuLG07CgppbnQgY2FzZXM7CgppbnQgaXNpdG9rKGludCBhLGludCBudGgsaW50IGIpewoKICAgIGJvb2wgb2theT10cnVlOwoKICAgIGlmKGRwM1thXT09MSl7CiAgICAgICAgb2theT1mYWxzZTsKICAgIH0KCiAgICBpZihkcDJbYV1bYl09PTEpewogICAgICAgIG9rYXk9ZmFsc2U7CiAgICB9CgogICAgaW50IHJldD0wOwoKICAgIGlmKG9rYXkpewogICAgaW50IGJhPWE7CiAgICBpbnQgYWI9YjsKCiAgICBjaGFyIHRlbXBbMTVdOwogICAgY2hhciB0ZW1wMlsxNV07CgogICAgZm9yKGludCBpPTA7aTxtO2krKyl7CiAgICAgICAgaWYoYSUyKXsKICAgICAgICAgICAgdGVtcFtpXT0nLic7CiAgICAgICAgICAgIHJldCsrOwogICAgICAgIH0KICAgICAgICBlbHNlewogICAgICAgICAgICB0ZW1wW2ldPSd4JzsKICAgICAgICB9CiAgICAgICAgYS89MjsKICAgIH0KCgogICAgZm9yKGludCBpPTA7aTxtO2krKyl7CiAgICAgICAgaWYodGVtcFtpXT09Jy4nICYmIGFycltudGhdW2ldPT0neCcpewogICAgICAgICAgICBva2F5PWZhbHNlOwogICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgLy9jb3V0PDxudGg8PGJhPDxhYjw8IuuKlDHtg4jrnb0iPDxlbmRsOwogICAgICAgIH0KICAgIH0gLy/slYnsnYQg7IiYIOyeiOuKlCDsnpDrpqzsnbjsp4Ag7ZmV7J24CgoKCgogICAgaWYob2theSl7CiAgICBmb3IoaW50IGk9MDtpPG0tMTtpKyspewogICAgICAgIGlmKHRlbXBbaV09PScuJyAmJiB0ZW1wW2krMV09PScuJyl7CiAgICAgICAgICAgIG9rYXk9ZmFsc2U7CiAgICAgICAgICAgIGRwM1tiYV09MTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIC8vY291dDw8bnRoPDxiYTw8YWI8PCLripQy7YOI6529Ijw8ZW5kbDsKICAgICAgICB9CiAgICB9Ly/qsJnsnbQg7JWJ7JWY64qU7KeAIO2ZleyduAoKICAgIGlmKG9rYXkpewoKICAgIGZvcihpbnQgaT0wO2k8bTtpKyspewogICAgICAgIGlmKGIlMil7CiAgICAgICAgICAgIHRlbXAyW2ldPScuJzsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgdGVtcDJbaV09J3gnOwogICAgICAgIH0KICAgICAgICBiLz0yOwogICAgfQoKICAgIGlmKG9rYXkpewoKICAgIGZvcihpbnQgaT0wO2k8bTtpKyspewogICAgICAgIGlmKGktMT49MCAmJiB0ZW1wW2ldPT0nLicgJiYgdGVtcDJbaS0xXT09Jy4nKXsKICAgICAgICAgICAgb2theT1mYWxzZTsKICAgICAgICAgICAgZHAyW2JhXVthYl09MTsKICAgICAgICAgICAgZHAyW2FiXVtiYV09MTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgIC8vY291dDw8bnRoPDxiYTw8YWI8PCLripQz7YOI6529Ijw8ZW5kbDsKICAgICAgICB9CiAgICAgICAgaWYoaSsxPG4gJiYgdGVtcFtpXT09Jy4nICYmIHRlbXAyW2krMV09PScuJyl7CiAgICAgICAgICAgIG9rYXk9ZmFsc2U7CiAgICAgICAgICAgIGRwMltiYV1bYWJdPTE7CiAgICAgICAgICAgIGRwMlthYl1bYmFdPTE7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAvL2NvdXQ8PG50aDw8YmE8PGFiPDwi64qUNO2DiOudvSI8PGVuZGw7CiAgICAgICAgfQogICAgfQoKICAgIH0KICAgIH0KICAgIH0KICAgIH0KCiAgICBpZihva2F5KXsKICAgICAgICByZXR1cm4gcmV0OwogICAgfQogICAgZWxzZXsKICAgICAgICByZXR1cm4gMDsKICAgIH0KfQoKaW50IG1haW4oKQp7CgogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKE5VTEwpOwogICAgY291dC50aWUoTlVMTCk7CgogICAgaW50IGM7CiAgICBjaW4+PmM7CgogICAgZm9yKGludCBpPTA7aTxjO2krKyl7CgogICAgICAgIGNpbj4+bj4+bTsKCiAgICAgICAgZm9yKGludCBpPTA7aTxuO2krKyl7CiAgICAgICAgICAgIGZvcihpbnQgaj0wO2o8bTtqKyspewogICAgICAgICAgICAgICAgYXJyW2ldW2pdPSdcMCc7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGNhc2VzPTE7CiAgICAgICAgZm9yKGludCBpPTA7aTxtO2krKyl7CiAgICAgICAgICAgIGNhc2VzKj0yOwogICAgICAgIH0KCiAgICAgICAgZm9yKGludCBpPTA7aTxuO2krKyl7CiAgICAgICAgICAgIGZvcihpbnQgaj0wO2o8Y2FzZXM7aisrKXsKICAgICAgICAgICAgICAgIGRwW2ldW2pdPTA7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGZvcihpbnQgaj0wO2o8bjtqKyspewogICAgICAgICAgICBjaW4+PmFycltqXTsKICAgICAgICB9CgogICAgICAgIGZvcihpbnQgaz0wO2s8Y2FzZXM7aysrKXsKICAgICAgICAgICAgZHBbMF1ba109aXNpdG9rKGssMCwwKTsKICAgICAgICB9CgoKICAgICAgICBmb3IoaW50IGk9MTtpPG47aSsrKXsKICAgICAgICAgICAgZm9yKGludCBrPTA7azxjYXNlcztrKyspewogICAgICAgICAgICAgICAgZm9yKGludCBqPTA7ajxjYXNlcztqKyspewogICAgICAgICAgICAgICAgICAgIGRwW2ldW2tdPW1heChkcFtpXVtrXSxkcFtpLTFdW2pdK2lzaXRvayhrLGksaikpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBpbnQgbWF4ZT0wOwoKICAgICAgICBmb3IoaW50IGo9MDtqPGNhc2VzO2orKyl7CiAgICAgICAgICAgIG1heGU9bWF4KG1heGUsZHBbbi0xXVtqXSk7CiAgICAgICAgfQoKCiAgICAgICAgY291dDw8bWF4ZTw8J1xuJzsKCiAgICB9Cn0K

Success #stdin #stdout 0s 4332KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/gQChIh

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language