제출 #1058931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058931		YassirSalama	Furniture (JOI20_furniture)	C++17	5 / 100	5060 ms	37972 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(),v.end()
#define pb push_back
#define F first
#define S second
const int maxn=1e3+100;
int arr[maxn][maxn];
bool r[maxn][maxn];
pair<int,int> par[maxn][maxn];
bool c[maxn][maxn];
int n,m;
bool bfs(){
    memset(r,false,sizeof(r));
    memset(c,0,sizeof(c));
    queue<pair<int,int>> q;
    q.push({0,0});
    par[0][0]={0,0};
    while(!q.empty()){
        pair<int,int> t=q.front();q.pop();
        int i=t.F;
        int j=t.S;
        if(arr[i][j]) continue;
        if(i+1<n&&!c[i+1][j]){
            q.push({i+1,j});
            par[i+1][j]={i,j};
            c[i+1][j]=1;
        }
        if(j+1<m&&!c[i][j+1]){
            par[i][j+1]={i,j};
            c[i][j+1]=1;
            q.push({i,j+1});
        }
    }
    if(!c[n-1][m-1]) return false;
    pair<int,int> t={n-1,m-1};
    r[0][0]=1;
    while(true){
        pair<int,int> x=par[t.F][t.S];
        r[t.F][t.S]=1;
        if(x.F==0&&x.S==0) break;
        t=x;
    }
    return true;
}
signed main(){
    ios_base::sync_with_stdio(NULL);cin.tie(0);
    cin>>n;
    cin>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }
    int q;
    cin>>q;
    bfs();
    while(q--){
        int x,y;
        cin>>x>>y;
        x--,--y;
        if(!r[x][y]){
            arr[x][y]=1;
            cout<<'1'<<endl;
        }else{
            arr[x][y]=1;
            bool c=bfs();
            if(!c){
                arr[x][y]=0;
                cout<<0<<endl;
                bfs();
                continue;
            }
            arr[x][y]=1;
            cout<<"1"<<endl;
        }

    }
}

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