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
Note: furniture.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
12152 KB |
Output is correct |
| 2 |
Incorrect |
220 ms |
16284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
12152 KB |
Output is correct |
| 2 |
Incorrect |
220 ms |
16284 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
