제출 #1181534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181534		omarrrr	Furniture (JOI20_furniture)	C++20	100 / 100	145 ms	11140 KiB

furniture

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second

using namespace std;

ll n,m,pos[2000],t[1100][1100];

void form(ll i,ll j){
    if(t[i][j])return;
    t[i][j]=1;
    pos[i+j]--;
   // if(i<0 || i>=n || j<0 || j>=n)return;
   bool good=true;
    if(i==0){
        if(j+1<m){
            form(i,j+1);
        }
        if(j && t[i+1][j-1]){
            form(i+1,j);
            form(i,j-1);
        }
        good=false;
    }
    if(i==n-1){
        if(j)
            form(i,j-1);
        if(j+1<m && t[i-1][j+1]){
            form(i,j+1);
            form(i-1,j);
        }
        good=false;
    }
    if(j==0){
        if(i+1<n)
            form(i+1,j);
        if(i && t[i-1][j+1]){
            form(i,j+1);
            form(i-1,j);
        }
        good=false;
    }
    if(j==m-1){
        if(i)
            form(i-1,j);
        if(i+1<n && t[i+1][j-1]){
            form(i+1,j);
            form(i,j-1);
        }
        good=false;
    }
    if(good){
        if(t[i-1][j+1]){
            form(i-1,j);
            form(i,j+1);
        }
        if(t[i+1][j-1]){
            form(i+1,j);
            form(i,j-1);
        }

    }



    return;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    memset(pos,0,sizeof(pos));
    queue<pair<ll,ll>>q;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<m;j++){
            pos[i+j]++;
            cin>>t[i][j];
            if(t[i][j]){
                q.push({i,j});
            }
            t[i][j]=0;
        }
    }
    while(!q.empty()){
        ll i=q.front().F,j=q.front().S;
        q.pop();
        if(!t[i][j]){
            form(i,j);
        }
//        cout<<i<<" "<<j<<"\n";
//        for(ll i=0;i<n;i++){
//            for(ll j=0;j<m;j++){
//                cout<<t[i][j]<<" ";
//            }
//            cout<<"\n";
//        }
    }
//    for(ll i=0;i<n+m;i++){
//        cout<<pos[i]<<" ";
//    }
    ll i,j,p;
    cin>>p;
    while(p--){
        cin>>i>>j;
        i--;j--;
        if(t[i][j]){
            cout<<"1\n";
        }else{
            if(pos[i+j]>1){
                cout<<"1\n";
                form(i,j);
            }else{
                cout<<"0\n";
            }
        }
    }


    return 0;
}
/*



3 7
0 0 1 0 0 0 0
1 0 0 1 0 1 0
0 1 0 0 0 0 0



 */

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