#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl "\n"
#define pii pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define pque priority_queue
#define pqueg priority_queue<ll,vector<ll>,greater<ll>>
#define que queue<ll>
#define FOR(m,i,n) for(int i=(m); i<=(n); i++)
#define FORM(m,i,n) for(int i=(m); i>=(n); i--)
#define all(v) sort(v.begin(),v.end())
ll n,m,qq,x,y;
queue<pii> q;
ll grid[1010][1010],d[1000100];
bool vis[1010][1010];
ll tempd[1000100];
vector<pii> v;
bool cek;
void bfs() {
cek = false;
while(!q.empty()) {
pii x = q.front();
q.pop();
v.pb({x.fi,x.se});
d[x.fi+x.se]--;
if(d[x.fi+x.se] == 0) {
cek = true;
return;
}
if(vis[x.fi+1][x.se-1] && !vis[x.fi+1][x.se] && x.fi < n) {
q.push({x.fi+1,x.se});
vis[x.fi+1][x.se] = true;
}
if(vis[x.fi-1][x.se+1] && !vis[x.fi][x.se+1] && x.se < m) {
q.push({x.fi,x.se+1});
vis[x.fi][x.se+1] = true;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
FOR(1,i,n) {
FOR(1,j,m) {
cin >> grid[i][j];
vis[i][j] = grid[i][j];
if(vis[i][j]) q.push({i,j});
d[i+j]++;
}
}
FOR(1,i,m) vis[0][i] = true;
FOR(1,i,n) vis[i][0] = true;
bfs();
v.clear();
cin >> qq;
while(qq--) {
cin >> x >> y;
if(vis[x][y]) {
cout << 1 << endl;
continue;
}
FOR(2,i,n+m) {
tempd[i] = d[i];
}
vis[x][y] = true;
q.push({x,y});
bfs();
if(cek) {
cout << 0 << endl;
vis[x][y] = 0;
for(auto i : v) {
vis[i.fi][i.se] = 0;
}
FOR(1,i,n+m) d[i] = tempd[i];
}
else {
cout << 1 << endl;
}
v.clear();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
