Submission #309941

#	Time	Username	Problem	Language	Result	Execution time	Memory
309941		ijxjdjd	Furniture (JOI20_furniture)	Java	0 / 100	168 ms	14056 KiB

furniture

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Iterator;
import java.io.IOException;
import java.util.AbstractSequentialList;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.LinkedList;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class furniture {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Furniture solver = new Furniture();
        solver.solve(1, in, out);
        out.close();
    }

    static class Furniture {
        LinkedList<Integer>[] cols;
        boolean[][] reachable;
        boolean[][] visited;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            int M = in.nextInt();
            reachable = new boolean[N + 2][M + 2];
            cols = new LinkedList[N + 2];
            visited = new boolean[N + 2][M + 2];
            for (int i = 0; i <= N + 1; i++) {
                cols[i] = new LinkedList<>();
                for (int j = 0; j <= M + 1; j++) {
                    cols[i].add(j);
                }
            }
            visited[N][M] = true;
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    if (in.nextInt() == 1) {
                        reachable[i][j] = false;
                    } else {
                        reachable[i][j] = true;
                    }
                }
            }
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= M; j++) {
                    start(i, j);
                }
            }
            int Q = in.nextInt();
            while (Q-- > 0) {
                int x = in.nextInt();
                int y = in.nextInt();
                boolean good = false;
                if (!reachable[x][y]) {
                    out.println(1);
                } else {
                    for (Iterator<Integer> iter = cols[x - 1].descendingIterator(); iter.hasNext(); ) {
                        int j = iter.next();
                        if (!reachable[x - 1][j]) {
                            iter.remove();
                        } else {
                            if (j > y) {
                                good = true;
                            }
                            break;
                        }
                    }
                    for (Iterator<Integer> iter = cols[x + 1].iterator(); iter.hasNext(); ) {
                        int j = iter.next();
                        if (!reachable[x + 1][j]) {
                            iter.remove();
                        } else {
                            if (j < y) {
                                good = true;
                            }
                            break;
                        }
                    }
                    if (good) {
                        out.println(1);
                        go(x, y);
                    } else {
                        out.println(0);
                    }
                }

            }
        }

        void go(int i, int j) {
            ArrayDeque<int[]> deque = new ArrayDeque<>();
            reachable[i][j] = false;
            deque.add(new int[]{i, j});
            while (deque.size() > 0) {
                int[] next = deque.removeFirst();
                if (!reachable[next[0] + 1][next[1] - 1]) {
                    if (reachable[next[0] + 1][next[1]]) {
                        deque.add(new int[]{next[0] + 1, next[1]});
                        reachable[next[0] + 1][next[1]] = false;
                    }
                }
                if (!reachable[next[0] - 1][next[1] + 1]) {
                    if (reachable[next[0]][next[1] + 1]) {
                        deque.add(new int[]{next[0], next[1] + 1});
                        reachable[next[0]][next[1] + 1] = false;
                    }
                }
            }
        }

        boolean start(int i, int j) {
            if (!reachable[i][j] || visited[i][j]) {
                return reachable[i][j];
            } else {
                visited[i][j] = true;
                reachable[i][j] = start(i + 1, j) || start(i, j + 1);
            }
            return reachable[i][j];
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

Compilation message (stderr)

Note: furniture.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

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