#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 1024;
bool has_a[N][N], has_b[N][N], has_furn[N][N];
int n, m;
void expand(int i, int j, bool a[N][N])
{
a[i][j] = 1;
for (int x : {i-1, i, i+1}) for (int y : {j-1, j, j+1}) {
if (x < 0 || n <= x || y < 0 || m <= y)
continue;
if (has_furn[x][y] && !a[x][y])
expand(x, y, a);
a[x][y] = 1;
}
}
bool put_furn(int i, int j)
{
if (has_a[i][j] && has_b[i][j])
return 0;
has_furn[i][j] = 1;
if (has_a[i][j]) {
expand(i, j, has_a);
LoopR (k,0,j) {
if (has_furn[i][k])
break;
put_furn(i, k);
}
Loop (k,i+1,n) {
if (has_furn[k][j])
break;
put_furn(k, j);
}
}
if (has_b[i][j]) {
expand(i, j, has_b);
Loop (k,j+1,m) {
if (has_furn[i][k])
break;
put_furn(i, k);
}
LoopR (k,0,i) {
if (has_furn[k][j])
break;
put_furn(k, j);
}
}
return 1;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> m;
Loop (i,0,n) {
has_a[i][0] = 1;
has_b[i][m-1] = 1;
}
Loop (j,0,m) {
has_a[n-1][j] = 1;
has_b[0][j] = 1;
}
Loop (i,0,n) Loop (j,0,m) {
int x;
cin >> x;
if (x)
put_furn(i, j);
}
int q;
cin >> q;
while (q--) {
int i, j;
cin >> i >> j;
cout << put_furn(i-1, j-1) << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
