提出 #72891711

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;
int dx[]{-1, -1, -1};
int dy[]{-1, 0, 1};

void solve()
{
    int n, c;
    cin >> n >> c;
    vector<string> s(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> s[i], s[i] = " " + s[i];
    vector<vector<int>> pre(n + 2, vector<int>(n + 2));
    for (int j = n; j; j--)
    {
        for (int i = n; i; i--)
        {
            pre[i][j] = pre[i + 1][j] + (s[i][j] == '#');
        }
    }
    queue<array<int, 2>> q;
    q.push({n, c});
    vector<int> dest(n + 1);
    vector<vector<int>> vis(n + 1, vector<int>(n + 1));
    while (q.size())
    {
        auto [x, y] = q.front();
        q.pop();
        if (vis[x][y])
            continue;
        vis[x][y] = 1;
        for (int i = 0; i < 3; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 or ny < 0 or ny > n)
                continue;
            if (s[nx][ny] == '.' and !vis[nx][ny])
            {
                q.push({nx, ny});
            }
            if (s[nx][ny] == '#')
            {
                if (!vis[nx][ny])
                {
                    if (pre[nx][ny] - dest[ny] == 1)
                    {
                        dest[ny]++;
                        q.push({nx, ny});
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)
        cout << vis[1][i];
    cout << "\n";
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--)
        solve();

    return 0;
}

提出情報

ジャッジ結果