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;
boolean[][] can = new boolean[N + 2][M + 2];
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;
can[i][j] = true;
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (!reachable[i][j]) {
go(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);
can[x][y] = false;
} 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);
can[x][y] = false;
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]][next[1] - 1]) {
deque.add(new int[]{next[0], next[1] - 1});
reachable[next[0]][next[1] - 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;
}
if (reachable[next[0] - 1][next[1]]) {
reachable[next[0] - 1][next[1]] = false;
deque.add(new int[]{next[0] - 1, next[1]});
}
}
}
}
}
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 |
152 ms |
13540 KB |
Output is correct |
| 2 |
Correct |
193 ms |
16300 KB |
Output is correct |
| 3 |
Correct |
194 ms |
15464 KB |
Output is correct |
| 4 |
Correct |
259 ms |
21612 KB |
Output is correct |
| 5 |
Correct |
270 ms |
20288 KB |
Output is correct |
| 6 |
Correct |
293 ms |
21436 KB |
Output is correct |
| 7 |
Correct |
251 ms |
22860 KB |
Output is correct |
| 8 |
Correct |
341 ms |
23888 KB |
Output is correct |
| 9 |
Correct |
293 ms |
22616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
13540 KB |
Output is correct |
| 2 |
Correct |
193 ms |
16300 KB |
Output is correct |
| 3 |
Correct |
194 ms |
15464 KB |
Output is correct |
| 4 |
Correct |
259 ms |
21612 KB |
Output is correct |
| 5 |
Correct |
270 ms |
20288 KB |
Output is correct |
| 6 |
Correct |
293 ms |
21436 KB |
Output is correct |
| 7 |
Correct |
251 ms |
22860 KB |
Output is correct |
| 8 |
Correct |
341 ms |
23888 KB |
Output is correct |
| 9 |
Correct |
293 ms |
22616 KB |
Output is correct |
| 10 |
Correct |
468 ms |
35860 KB |
Output is correct |
| 11 |
Correct |
257 ms |
17812 KB |
Output is correct |
| 12 |
Correct |
1749 ms |
137996 KB |
Output is correct |
| 13 |
Correct |
1022 ms |
112220 KB |
Output is correct |
| 14 |
Correct |
2257 ms |
197448 KB |
Output is correct |
| 15 |
Correct |
2160 ms |
192912 KB |
Output is correct |
| 16 |
Correct |
1822 ms |
194476 KB |
Output is correct |
| 17 |
Correct |
1848 ms |
189912 KB |
Output is correct |
| 18 |
Correct |
1895 ms |
204912 KB |
Output is correct |
| 19 |
Correct |
2295 ms |
211320 KB |
Output is correct |
| 20 |
Correct |
1900 ms |
209544 KB |
Output is correct |
| 21 |
Correct |
2024 ms |
209632 KB |
Output is correct |
