oj.uz

답안 #1004376

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004376 2024-06-21T08:22:51 Z Nailuj_217 Furniture (JOI20_furniture) C++17
0 / 100
 29 ms 2392 KB 
#include <bits/stdc++.h>
#define l long long
using namespace std;

const l LEN = 1005;
l n, m;

array<array<bool, LEN>, LEN> grid;
array<array<bool, 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;
    if (x != 1 && dfsback(x-1, y)) return true;
    if (y != 1 && dfsback(x, y-1)) return true;
    return false;
}



int main() {


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


    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) top = dfsback(x-1, y);
        else top = true;
        if (y != 1) left = dfsback(x, y-1);
        else left = true;
        if (top && left) {
            possible = updatepossible;
            grid[x][y] = true;
            cout << 1 << "\n";
        } else {
            cout << 0 << "\n";
        }




    }


	cout << flush;





    return 0;
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -