Submission #72908483

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std;
using ll = long long;
using db = double;
const ll N = 1e6 + 5;
const ll md = 998244353;
const ll MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db eps = 1e-6;
typedef pair<ll, ll> PLL;
#define fi first
#define se second

char g[3005][3005];
ll cnt[2][3005];
ll ans[3005];
ll n, y;

void solve() 
{
    cin >> n >> y;
    for (ll i = 1; i <= n; i++) 
    {
        for (ll j = 1; j <= n; j++) 
            cin >> g[i][j];
        cnt[0][i] = 0;
        cnt[1][i] = 0;
        ans[i] = 0;
    }

    for (ll j = 1; j <= n; j++) 
    {
        if(g[n][j] == '#')
            cnt[0][j] = 1;
    }

    set<ll> q1, q2;
    q1.insert(y);
    ll k = 0;
    for (ll i = n - 1; i >= 1; i--) 
    {
        k = 1 - k;
        q2.clear();

        for (auto f : q1) 
        {
            for (ll to : {f - 1, f, f + 1}) 
            {
                if (to < 1 || to > n) 
                    continue;

                if (g[i][to] != '#') 
                    q2.insert(to);
                else 
                {
                    if (cnt[1 - k][to] == 0) 
                    {
                        q2.insert(to);
                        g[i][to] = '.';
                    }
                }
            }
        }

        for (ll j = 1; j <= n; j++) 
        {
            cnt[k][j] = cnt[1 - k][j];
            if(g[i][j] == '#')
               cnt[k][j]++;
        }
        q1 = q2;
    }

    for (auto f : q1) 
        ans[f] = 1;

    for (ll j = 1; j <= n; j++) 
        cout << ans[j];
    cout << '\n';
}

int main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) 
    {
        solve();
    }
    return 0;
}

Submission Info

Judge Result