#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=1005,mod=1e9+7;
int t,a[N][N],p[N][N][2],c[N][N][2],n,m,s[N][N][2],q;
set<int> st[N];
bool ok(int x,int y){
if(min(x,y)<1 || x>n || y>m) return 0;
return 1;
}
void dfs1(int x,int y,int c){
if(p[x][y][c]) return;
p[x][y][c] = 1;
if(ok(x+1,y) && a[x+1][y]!=1) dfs1(x+1,y,0);
if(ok(x,y+1) && a[x][y+1]!=1) dfs1(x,y+1,1);
}
void dfs2(int x,int y,int c){
if(s[x][y][c]) return;
s[x][y][c] = 1;
if(ok(x-1,y) && a[x-1][y]!=1) dfs2(x-1,y,0);
if(ok(x,y-1) && a[x][y-1]!=1) dfs2(x,y-1,1);
}
void go(int x,int y,int b){
if(!c[x][y][b] && !c[x][y][1-b]) return;
c[x][y][b]--;
if(!c[x][y][b^1]) st[y].erase(x);
if(ok(x+1,y) && a[x+1][y]!=1) go(x+1,y,0);
if(ok(x,y+1) && a[x][y+1]!=1) go(x,y+1,1);
}
main(){
// t=1;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
dfs1(1,1,0);
dfs2(n,m,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(max(p[i][j][0],p[i][j][1]) && max(s[i][j][0],s[i][j][1])) c[i][j][0] = s[i][j][0] ,
c[i][j][1] = s[i][j][1];
if(c[i][j][1]) st[j].insert(i);
}
}
cin >>q;
while(q--){
int x,y;
cin >> x >> y;
if(st[y].size() && (*st[y].begin()!=x || *--st[y].end()!=x) ) {
cout<<1<<endl;
go(x,y,0);
}
else cout<<0<<endl;
}
}
Compilation message
furniture.cpp:32:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
32 | main(){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5056 ms |
2124 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5056 ms |
2124 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
