Submission #478978

#	Time	Username	Problem	Language	Result	Execution time	Memory
478978		nicolaalexandra	Furniture (JOI20_furniture)	C++14	5 / 100	5066 ms	17960 KiB

furniture

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

int a[DIM][DIM],viz[DIM][DIM];
deque <pair<int,int> > c,w;
int n,m,i,j,q,x,y;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            cin>>a[i][j];

    for (i=0;i<=m+1;i++)
        a[0][i] = a[n+1][i] = 1;
    for (i=1;i<=n;i++)
        a[i][0] = a[i][m+1] = 1;


    c.push_back(make_pair(1,1));
    viz[1][1] = 1;
    while (!c.empty()){
        int i = c.front().first;
        int j = c.front().second;
        c.pop_front();
        if (!a[i][j+1] && !viz[i][j+1]){
            c.push_back(make_pair(i,j+1));
            viz[i][j+1] = 1;
        }
        if (!a[i+1][j] && !viz[i+1][j]){
            c.push_back(make_pair(i+1,j));
            viz[i+1][j] = 1;
        }
    }

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (!viz[i][j] && !a[i][j])
                a[i][j] = 1;


    cin>>q;
    for (;q--;){
        cin>>x>>y;

        c.clear(), w.clear();
        c.push_back(make_pair(x,y));
        w.push_back(make_pair(x,y));
        a[x][y] = 1;

        int ok = 1;
        while (!c.empty()){
            int i = c.front().first;
            int j = c.front().second;
            c.pop_front();

            if (i == n && j == m){
                ok = 0;
                break;
            }

            if (!a[i][j+1] && a[i-1][j+1]){
                c.push_back(make_pair(i,j+1));
                w.push_back(make_pair(i,j+1));
                a[i][j+1] = 1;
            }

            if (!a[i+1][j] && a[i+1][j-1]){
                c.push_back(make_pair(i+1,j));
                w.push_back(make_pair(i+1,j));
                a[i+1][j] = 1;
            }

        }

        cout<<ok<<"\n";

        if (!ok){
            /// trb sa demarchez
            for (auto it : w)
                a[it.first][it.second] = 0;
        }

    }


    return 0;
}

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