#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e15 + 7, inf = 1e16;
const int mxn = 2e3 + 5;
int n, m, q;
int a[1005][1005];
int cnt[2005];
bool bad[1005][1005];
bool ck(int x, int y){
if(x == n && y == m)return(0);
if(bad[x][y])return(0);
if(bad[x + 1][y] && bad[x][y + 1])return(1);
if(bad[x - 1][y] && bad[x][y - 1])return(1);
return(0);
}
bool inside(int x, int y){
return(x >= 1 && y >= 1 && x <= n && y <= m);
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> a[i][j];
if(a[i][j] == 1){
bad[i][j] = 1;
}else{
cnt[i + j]++;
}
}
}
for(int i = 1; i <= n; i++)bad[i][m + 1] = 1;
for(int i = 1; i <= m; i++)bad[n + 1][i] = 1;
queue<pii>q;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(a[i][j] == 1){
for(int k = 0; k < 4; k++){
if(inside(i + x[k], j + y[k]) && !bad[i + x[k]][j + y[k]]){
q.push({i + x[k], j + y[k]});
}
}
}
}
}
while(!q.empty()){
auto [cox, coy] = q.front(); q.pop();
//cout << cox << ' ' << coy << " ";
if(ck(cox, coy)){
bad[cox][coy] = 1; cnt[cox + coy]--;
for(int i = 0; i < 4; i++){
int nwx = cox + x[i], nwy = coy + y[i];
if(inside(nwx, nwy) && !bad[nwx][nwy]){
q.push({nwx, nwy});
}
}
}
}
int qq; cin >> qq;
while(qq--){
int cox, coy; cin >> cox >> coy;
assert(cnt[cox + coy] >= 1);
if(bad[cox][coy]){
cout << 1 << "\n";
}
else if(cnt[cox + coy] == 1){
cout << 0 << "\n";
continue;
}else{
cout << 1 << "\n";
int xx = cox, yy = coy;
bad[cox][coy] = 1; cnt[cox + coy]--;
for(int i = 0; i < 4; i++){
int nwx = cox + x[i], nwy = coy + y[i];
if(inside(nwx, nwy) && !bad[nwx][nwy]){
q.push({nwx, nwy});
}
}
while(!q.empty()){
auto [cox, coy] = q.front(); q.pop();
if(ck(cox, coy)){
assert(cox == xx || cox + coy != xx + yy);
bad[cox][coy] = 1; cnt[cox + coy]--;
for(int i = 0; i < 4; i++){
int nwx = cox + x[i], nwy = coy + y[i];
if(inside(nwx, nwy) && !bad[nwx][nwy]){
q.push({nwx, nwy});
}
}
}
}
}
}
return(0);
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:67:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
67 | auto [cox, coy] = q.front(); q.pop();
| ^
furniture.cpp:102:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
102 | auto [cox, coy] = q.front(); q.pop();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
1548 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
1548 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
