제출 #1033507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1033507		vjudge1	Furniture (JOI20_furniture)	C++17	5 / 100	5032 ms	10420 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
bitset<1010> reach[1010], open[1010];
int n,m;
void redo(){    
    reach[0][1]=1;
    for(int i=1;i<=m;i++) {
        reach[i]=reach[i-1]&open[i];
        for(int j=2;j<=n;j++)
            if(open[i][j]&&reach[i][j-1])
                reach[i][j]=1;
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int q;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            open[j][i]=!x;
        }
    redo();
    cin>>q;
    for(int i=1;i<=q;i++) {
        int X,Y;
        cin>>Y>>X;
        queue<pair<int,int>>q;
        q.push({X,Y});
        reach[X][Y]=0;
        while(q.size()){
            auto[a,b]=q.front();
            q.pop();
            if(reach[a+1][b]&&!reach[a+1][b-1])
                q.push({a+1,b}),reach[a+1][b]=0;
            if(reach[a][b+1]&&!reach[a-1][b+1])
                q.push({a,b+1}),reach[a][b+1]=0;
        }
        if(reach[m][n]){
            cout<<"1\n";
            open[X][Y]=0;
        } else redo(),
            cout<<"0\n";
    }
}

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