제출 #773222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
773222		CyberCow	Furniture (JOI20_furniture)	C++17	100 / 100	313 ms	18052 KiB

furniture

//#include <bits/stdc++.h>
#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);
const int N = 1005;
int a[N][N];
int has[N][N];
int color[N][N], color1[N][N];
int hasan[N][N];
int ankqan[3 * N];

void solve()
{
    int n, i, j, m, x, y;
    cin >> n >> m;
    for ( i = 1; i <= n; i++)
    {
        for ( j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
    }
    queue<pair<int, int>> q;
    color[1][1] = 1;
    q.push({ 1, 1 });
    while (!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        if (x + 1 <= n && color[x + 1][y] == 0 && a[x + 1][y] == 0)
        {
            color[x + 1][y] = 1;
            q.push({ x + 1, y });
        }
        if (y + 1 <= m && color[x][y + 1] == 0 && a[x][y + 1] == 0)
        {
            color[x][y + 1] = 1;
            q.push({ x, y + 1 });
        }
    }
    color1[n][m] = 1;
    q.push({ n, m });
    while (!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        if (x - 1 >= 1 && color1[x - 1][y] == 0 && a[x - 1][y] == 0)
        {
            color1[x - 1][y] = 1;
            q.push({ x - 1, y });
        }
        if (y - 1 >= 1 && color1[x][y - 1] == 0 && a[x][y - 1] == 0)
        {
            color1[x][y - 1] = 1;
            q.push({ x, y - 1 });
        }
    }
    for ( i = 1; i <= n; i++)
    {
        for ( j = 1; j <= m; j++)
        {
            if (color[i][j] == 1 && color1[i][j] == 1)
            {
                hasan[i][j] = 1;
                ankqan[i + j]++;
            }
        }
    }
    int qq;
    cin >> qq;
    for ( i = 0; i < qq; i++)
    {
        cin >> x >> y;
        if (hasan[x][y] == 0)
        {
            cout << 1 << '\n';
            continue;
        }
        if (ankqan[x + y] == 1)
        {
            cout << 0 << '\n';
            continue;
        }
        cout << 1 << '\n';
        q.push({ x, y });
        while (!q.empty())
        {
            x = q.front().first;
            y = q.front().second;
            q.pop();
            hasan[x][y] = 0;
            ankqan[x + y]--;
            if (hasan[x - 1][y + 1] == 0)
            {
                if (hasan[x - 1][y] == 1)
                {
                    q.push({ x - 1, y });
                }
                if (hasan[x][y + 1] == 1)
                {
                    q.push({ x, y + 1 });
                }
            }
            if (hasan[x + 1][y - 1] == 0)
            {
                if (hasan[x + 1][y] == 1)
                {
                    q.push({ x + 1, y });
                }
                if (hasan[x][y - 1] == 1)
                {
                    q.push({ x, y - 1 });
                }
            }
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95