Source Code
//#define Print 1
#include <iostream>
#include <complex>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// vector push_back push front top empty pop make_pair long long insert begin end  
#define int long long
typedef long long ll;
typedef vector<int> vi;
typedef vector<pair <int,int> > vpi;
typedef vector<long long> vll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
void display(vi &a){for(int z : a)cout << z << " ";cout << endl;}
#ifdef Print
    #define trace(x) cerr<<__FUNCTION__<<":"<<__LINE__<<": "#x" = "<<x<<endl;
#else
    #define trace(x);
#endif
#define F first
#define ln '\n'
#define S second
#define PB push_back
#define MP make_pair
#define B begin()
#define RB rbegin()
#define E end()
#define RE rend()
#define Z size()
#define REP(i,a,b) for (int i = a; i < b; i++)
#define L length()
#define show(a) cerr << " *** " << a << endl;
#define show1(a) cerr << " /// " << a << endl;
#define valid(a,b,c) (a >= b && a < c ? 1 : 0)
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int mod = (int)1e9 + 7;
const ll INF64 = 3e18;
void smxl(ll &a, ll b){if (a < b)a=b;}
void smnl(ll &a, ll b){if (a > b)a=b;}
void adsl(ll &a, ll b){a += b;if (a >= mod)a -= mod;}
void misl(ll &a, ll b){a -= b;if (a >= mod)a -= mod; if (a < 0)a += mod;}
void smx(ll &a, ll b){if (a < b)a=b;}
void smn(ll &a, ll b){if (a > b)a=b;}
void ads(ll &a, ll b){a += b;if (a >= mod)a -= mod;}
void mis(ll &a, ll b){a -= b;if (a >= mod)a -= mod; if (a < 0)a += mod;}
ll gcd(ll a, ll b) {return (b==0? a:gcd(b,a%b));}
ll egcd(ll a, ll b, ll & x, ll & y) {if (a == 0){x = 0;y = 1;return b;}ll x1, y1;ll d = egcd(b % a, a, x1, y1);x = y1 - (b / a) * x1;y = x1;return d;}
ll mbinp(ll a, ll b){a %= mod;if (b == 0)return 1;ll ans = mbinp(a, b/2);ll tmp = (ans * ans) % mod;if (b % 2)return ((tmp * a) % mod);return ((tmp) % mod);}
ll binp(ll a, ll b){if (b == 0)return 1;ll ans = binp(a, b/2);ll tmp = (ans * ans);if (b % 2)return ((tmp * a));return ((tmp));}
long long C(int n, int m){ll ret=1;for(int i=1;i<=m;i++){ret*=(n-i+1);ret/=i;}return ret;}
long long overbinp(long long a, int b){long long res = 1;while (b){if (b & 1){if (res < INF64 / a) res *= a;else return INF64;}if (b > 1){if (a < INF64 / a) a *= a;else return INF64;}b >>= 1;}return res;}

//double triarea(double a, double b, double c){double p= (a+b+c)/2;return (sqrt(p*(p-a)*(p-b)*(p-c)));}
//ll diag(ll n){return ((n*(n-1))/2 - n);}
//*find_by_order
//order_of_key
//number of divs of n=p^a*q^b*r^c  == (a+1)*(b+1)*(c+1)
//sum of divs of n=p^a*q^b*r^c  == (p^(a+1)-1)/(p-1) * (q^(b+1)-1)/(q-1) * (r^(c+1)-1)/(r-1)
//prod of divs of n=p^a*q^b*r^c  == n ^ (((a+1)*(b+1)*(c+1))/2)

struct DSU{
    vi par;
    vi siize;
    DSU(int n)
    {
        par.resize(n);
        siize.resize(n);
        REP(i,0,n)
        {
            par[i]=i;
            siize[i]=1;
        }
    }
    int get(int x)
    {
        return (x == par[x] ? x : par[x] = get(par[x]));
    }
    void merge(int a, int b)
    {
        int x = get(a);
        int y = get(b);
        if (x == y)return;
        if (siize[x] < siize[y])swap(x,y);par[y] = x;siize[x] += siize[y];
    }
    int soze(int x)
    {
        return siize[x];
    }
};

const int md = 998244353;
char tab[2005][2005];
char pab[1005][1005];
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,m;
    cin >>n >> m;
    REP(i,0,n)
        REP(j,0,m)
            cin >>pab[i][j];
    int n1 = 2*n-1;
    int m1 = 2*m-1;
    REP(i,0,n1)
        REP(j,0,m1)
            tab[i][j] = '-';
    REP(i,0,n)
        REP(j,0,m)
            tab[2*i][2*j] = pab[i][j];
/*    REP(i,0,n1)
    {
        REP(j,0,m1)
            cout << tab[i][j] << " ";
        cout << endl;
    }
    cout << endl << endl;*/
    n = n1;
    m = m1;
    DSU dsu = DSU(n*m);
    REP(i,0,n)
        REP(j,0,m)
            if (tab[i][j] == '.')
                REP(k,0,4)
                    if (valid(i+dx[k],0,n) && valid(j+dy[k],0,m) && (tab[i+dx[k]][j+dy[k]] == '.' || tab[i+dx[k]][j+dy[k]] == '-'))
                        dsu.merge(i*m+j,(i+dx[k])*m+j+dy[k]);
    REP(i,0,n)
        REP(j,0,m)
        {
            if (tab[i][j] == '/')
            {
                if (valid(j+1,0,m) && valid(i+1,0,n) && (tab[i][j+1] == '.' || tab[i][j+1] == '-') &&(tab[i+1][j] == '.' || tab[i+1][j] == '-'))
                    dsu.merge(i*m+j+1,(i+1)*m+j);
                if (valid(j-1,0,m) && valid(i-1,0,n) && (tab[i][j-1] == '.' || tab[i][j-1] == '-') &&(tab[i-1][j] == '.' || tab[i-1][j] == '-'))
                    dsu.merge(i*m+j-1,(i-1)*m+j);
            }
            if (tab[i][j] == '\\')
            {
                if (valid(j-1,0,m) && valid(i+1,0,n) && (tab[i][j-1] == '.' || tab[i][j-1] == '-') &&(tab[i+1][j] == '.' || tab[i+1][j] == '-'))
                    dsu.merge(i*m+j-1,(i+1)*m+j);
                if (valid(j+1,0,m) && valid(i-1,0,n) && (tab[i][j+1] == '.' || tab[i][j+1] == '-') &&(tab[i-1][j] == '.' || tab[i-1][j] == '-'))
                    dsu.merge(i*m+j+1,(i-1)*m+j);
            }       
        }
    vi has(n*m,0);
/*    REP(i,0,n)
    {
        REP(j,0,m) 
        {
            cout << dsu.get(i*m+j) << " ";
        }
        cout << endl;
    }*/
    REP(i,0,n)
        REP(j,0,m) 
            if (tab[i][j] == '-')
                has[dsu.get(i*m+j)]++;
    int out = 0;
    REP(i,0,n)
        REP(j,0,m) 
        {
            if ((i == 0 || i == n-1) && tab[i][j] == '.')
                out = max(out,dsu.soze(dsu.get(i*m+j))-has[dsu.get(i*m+j)]);
            if ((j == 0 || j == m-1) && tab[i][j] == '.')
                out = max(out,dsu.soze(dsu.get(i*m+j))-has[dsu.get(i*m+j)]);
        }
    cout << out;
}
Copy
Mirrors Jalalium
GNU G++17
0 ms
656 KB
Wrong Answer