#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)
const int N = 1e3 + 10;
int n, m, q;
int t[N][N];
int c[N][N];
pii qu[N * N];
int ca[N][N];
int dis[N][N];
int cnt[N * N];
int ans[N * N];
int dfs(int x, int y) {
if (x >= n or y >= m) return 1e9;
if (c[x][y]) return 1e9;
if (ca[x][y] != -1) return dis[x][y];
dis[x][y] = min(dis[x][y], min(dfs(x + 1, y) + 1, dfs(x, y + 1) + 1));
ca[x][y] = 0;
return dis[x][y];
}
bool can(int k) {
if (k == q) return 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
c[i][j] = t[i][j];
dis[i][j] = 1e9;
}
}
for (int i = 0; i <= k; i++) {
c[qu[i].F - 1][qu[i].S - 1] = 1;
}
memset(ca, -1, sizeof ca);
ca[n - 1][m -1] = 1;
dis[n - 1][m -1] = 0;
dfs(0, 0);
return dis[0][0] < 1e9;
}
int main() {
FIO;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> t[i][j];
}
}
cin >> q;
for (int i = 0; i < q; i++) {
cin >> qu[i].F >> qu[i].S;
}
int l = 0;
int r = q;
while (l < r) {
int mid = (l + r) / 2;
if (can(mid)) {
l = mid + 1;
} else {
r = mid;
}
}
for (int i = 0; i < l; i++) {
ans[i] = 1;
}
can(l - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (dis[i][j] < 1e9) cnt[dis[i][j]]++;
}
}
for (int i = l + 1; i < q; i++) {
int x = qu[i].F - 1;
int y = qu[i].S - 1;
if (dis[x][y] < 1e9 and cnt[dis[x][y]] == 1) {
ans[i] = 0;
} else {
ans[i] = 1;
if (dis[x][y] < 1e9) cnt[dis[x][y]]--;
}
}
for (int i = 0; i < q; i++) {
cout << ans[i] << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |