Submission #1004461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004461		Nailuj_217	Furniture (JOI20_furniture)	C++17	100 / 100	4448 ms	12620 KiB

furniture

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

const l LEN = 1005;
l n, m;

array<bitset<LEN>, LEN> grid;
array<bitset<LEN>, LEN> possible, visited, updatepossible;

bool dfs(l x, l y) {
    if (visited[x][y]) return possible[x][y];
    visited[x][y] = true;
    if (grid[x][y]) return possible[x][y] = false;
    if (x == n && y == m) return possible[x][y] = true;
    if (x != n)
        if (dfs(x+1, y)) possible[x][y] = true;
    if (y != m) 
        if (dfs(x, y+1)) possible[x][y] = true;

    return possible[x][y];
}

bool dfsback(l x, l y) {
    if (!updatepossible[x][y]) return false;
    if (grid[x][y]) return false;
    if (x != n && updatepossible[x+1][y]) return true;
    if (y != m && updatepossible[x][y+1]) return true;
    updatepossible[x][y] = false;
    bool isval = false;
    if (x != 1 && dfsback(x-1, y)) isval = true;
    if (y != 1 && dfsback(x, y-1)) isval = true;
    return isval;
}



int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

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

        }


    dfs(1, 1);

    l q, x, y;
    bool left, top;
    cin >> q;
    while (q--) {
        cin >> x >> y;
        if (!possible[x][y]) {
            grid[x][y] = true;
            cout << 1 << "\n";
            continue;
        }
        updatepossible = possible;
        updatepossible[x][y] = false;
        if (x != 1) dfsback(x-1, y);
        if (y != 1) dfsback(x, y-1);
        if (x != 1) dfsback(x-1, y);
        // if (top || left) {
        //     if (x != 1 && top) top = dfsback(x-1, y);
        //     if (y != 1 && left) left = dfsback(x, y-1);
        // }
        if (updatepossible[1][1]) {
            possible = updatepossible;
            grid[x][y] = true;
            cout << 1 << "\n";
        } else {
            cout << 0 << "\n";
        }




    }

    return 0;
}
/*
6 8
0 0 0 0 0 0 0 0  
0 1 0 0 0 0 1 0
0 1 0 0 1 1 1 0
0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
100
4 6
1 2
6 1
5 1
4 1
3 1
2 1
6 2
6 3
4 3
4 4
4 8
5 8




6 8
0 0 0 0 0 0 0 0  
0 1 0 0 0 0 1 0
0 1 0 0 1 1 1 0
0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
100



6 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
100
2 2
1
3 2
1
4 2
1
5 2
1
5 1
1
4 1
1
3 1
1
2 1
1
1 4
1
2 4
1
2 5
1
1 5
1
4 4
1
3 3
0
4 5
1
5 4
1
5 5
0

*/

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:56:10: warning: unused variable 'left' [-Wunused-variable]
   56 |     bool left, top;
      |          ^~~~
furniture.cpp:56:16: warning: unused variable 'top' [-Wunused-variable]
   56 |     bool left, top;
      |                ^~~

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