2575. Separate Connections

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;


char mp[20][20];
int dp[1 << 18];
int dfs(int pat){
    if(dp[pat] != -1)return dp[pat];
    //cout << pat << " ";
    int maxans = 0;
    for(int i = 0; i < 18; ++i){
        if((pat>>i) & 1){
            for(int j = 0; j < 18; ++j){
                if( ((pat>>j) & 1) && mp[i][j]=='Y'){
                    maxans = max(maxans, 2 + dfs(pat ^ (1<<i) ^ (1<<j)));
                }
            }
        }
    }
    dp[pat]=maxans;
    return maxans;
}
int main(){
    int n, m;  cin >> n;
    while(n--){
        cin>>m;
        memset(dp, -1, sizeof dp);
        for(int i=0;i<m;++i)
        for(int j=0;j<m;++j){
            cin>>mp[i][j];
        }
        cout << dfs((1<<m) -1) << endl;
    }
}