제출 #784572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
784572		hanifchdn	Furniture (JOI20_furniture)	C++14	0 / 100	3 ms	1236 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second

const int dx1[] = {0, 1};
const int dy1[] = {1, 0};
const int dx2[] = {0, 1, 0, -1};
const int dy2[] = {1, 0, -1, 0}; 

int n, m;
bool a[1005][1005], check[1005][1005], vis[1005][1005];
set<int> s1[1005], s2[1005];

void df1(int x, int y) {
    vis[x][y] = 1;
    if (a[x][y]) return;
    for (int i = 0; i < 2; i++) {
        int tx = x + dx1[i], ty = y + dy1[i];
        if (tx > n or ty > m) continue;
        if (!vis[tx][ty]) df1(tx, ty);
        check[x][y] |= check[tx][ty];
    }
}

void dfs2(int x, int y, int h1, int w1, int h2, int w2) {
    check[x][y] = 0;
    s1[y].erase(x), s1[y + 1].erase(x), s2[x].erase(y), s2[x + 1].erase(y);
    for (int i = 0; i < 4; i++) {
        int tx = x + dx2[i], ty = y + dy2[i];
        if (tx > h2 or tx < h1 or ty > w2 or ty > w1 or !check[tx][ty]) continue;
        dfs2(tx, ty, h1, w1, h2, w2);
    }
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    }
    vis[n][m] = 1, check[n][m] = 1;
    df1(1, 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (check[i][j] and check[i][j - 1]) s1[j].insert(i);
            if (check[i][j] and check[i - 1][j]) s2[i].insert(j);
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (!check[x][y]) cout << 1 << "\n";
        else {
            auto it1 = s1[y].upper_bound(x), it2 = s2[x].upper_bound(y);
            if (it1 == s1[y].end() and it2 == s2[x].end()) {
                cout << 0 << "\n";
                continue;
            }
            cout << 1 << "\n";
            int h1 = x, w1 = y, h2 = x, w2 = y;
            for (int i = x - 1; i >= 1; i--) {
                if (check[i][y] and !check[i][y + 1]) h1 = i;
                else break;
            }
            for (int i = x + 1; i <= n; i++) {
                if (check[i][y] and !check[i][y - 1]) h2 = i;
                else break;
            }
            for (int j = y - 1; j >= 1; j--) {
                if (check[x][j] and !check[x + 1][j]) w1 = j;
                else break;
            }
            for (int j = y + 1; y <= m; y++) {
                if (check[x][j] and !check[x - 1][j]) w2 = j;
                else break;
            }
            dfs2(x, y, h1, w1, h2, w2);
        }
    }
}  

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