//#include <bits/stdc++.h>
#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define fr first
#define sc second
#define ad push_back
using namespace std;
using ll = long long;
mt19937 rnd(348502);
const int N = 1005;
int a[N][N];
int has[N][N];
int color[N][N], color1[N][N];
int hasan[N][N];
int ankqan[3 * N];
void solve()
{
int n, i, j, m, x, y;
cin >> n >> m;
for ( i = 1; i <= n; i++)
{
for ( j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
queue<pair<int, int>> q;
color[1][1] = 1;
q.push({ 1, 1 });
while (!q.empty())
{
x = q.front().first;
y = q.front().second;
q.pop();
if (x + 1 <= n && color[x + 1][y] == 0 && a[x + 1][y] == 0)
{
color[x + 1][y] = 1;
q.push({ x + 1, y });
}
if (y + 1 <= m && color[x][y + 1] == 0 && a[x][y + 1] == 0)
{
color[x][y + 1] = 1;
q.push({ x, y + 1 });
}
}
color1[n][m] = 1;
q.push({ n, m });
while (!q.empty())
{
x = q.front().first;
y = q.front().second;
q.pop();
if (x - 1 >= 1 && color1[x - 1][y] == 0 && a[x - 1][y] == 0)
{
color1[x - 1][y] = 1;
q.push({ x - 1, y });
}
if (y - 1 >= 1 && color1[x][y - 1] == 0 && a[x][y - 1] == 0)
{
color1[x][y - 1] = 1;
q.push({ x, y - 1 });
}
}
for ( i = 1; i <= n; i++)
{
for ( j = 1; j <= m; j++)
{
if (color[i][j] == 1 && color1[i][j] == 1)
{
hasan[i][j] = 1;
ankqan[i + j]++;
}
}
}
int qq;
cin >> qq;
for ( i = 0; i < qq; i++)
{
cin >> x >> y;
if (hasan[x][y] == 0)
{
cout << 1 << '\n';
continue;
}
if (ankqan[x + y] == 1)
{
cout << 0 << '\n';
continue;
}
cout << 1 << '\n';
q.push({ x, y });
while (!q.empty())
{
x = q.front().first;
y = q.front().second;
q.pop();
hasan[x][y] = 0;
ankqan[x + y]--;
if (y + 1 <= m && x - 1 >= 1 && hasan[x - 1][y + 1] == 0)
{
if (hasan[x - 1][y] == 1)
{
q.push({ x - 1, y });
}
if (hasan[x][y + 1] == 1)
{
q.push({ x, y + 1 });
}
}
if (x + 1 <= n && y - 1 >= 1 && hasan[x + 1][y - 1] == 0)
{
if (hasan[x + 1][y] == 1)
{
q.push({ x + 1, y });
}
if (hasan[x][y - 1] == 1)
{
q.push({ x, y - 1 });
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1748 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1876 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
1748 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
