Submission #684096

#	Time	Username	Problem	Language	Result	Execution time	Memory
684096		Darren0724	Furniture (JOI20_furniture)	C++17	100 / 100	1449 ms	6472 KiB

furniture

#include<bits/stdc++.h>
using namespace std;

vector<int> cnt(2050);
vector<vector<int>> v;
void dfs(int a,int b){
    v[a][b]=1;
    cnt[a+b]--;
    if(v[a-1][b+1]){
        if(v[a][b+1]==0){
            dfs(a,b+1);
        }
        if(v[a-1][b]==0){
            dfs(a-1,b);
        }
    }
    if(v[a+1][b-1]){
        if(v[a+1][b]==0){
            dfs(a+1,b);
        }
        if(v[a][b-1]==0){
            dfs(a,b-1);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    v.resize(n+2,vector<int>(m+2,1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cnt[i+j]++;
            v[i][j]=0;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int p;cin>>p;
            if(p==1){
                if(v[i][j]==0){
                    dfs(i,j);
                }
            }
        }
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int a,b;cin>>a>>b;
        if(v[a][b]==1){
            cout<<1<<endl;
            continue;
        }
        if(cnt[a+b]<=1){
            cout<<0<<endl;
        }
        else{
            cout<<1<<endl;
            dfs(a,b);
        }

    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<v[i][j]<<' ';
        }
        cout<<endl;
    }
    */

    return 0;
}

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