#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define lb lower_bound
#define ub upper_bound
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define bg(x) (x).begin()
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl
#define endl (char)(10)
#define arr(x) array<int , (x)>
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
ll Sum(ll a , ll b , ll MOD)
{
a %= MOD;
b %= MOD;
a += b;
return a % MOD;
}
ll Mul(ll a , ll b , ll MOD)
{
a %= MOD;
b %= MOD;
a *= b;
return a % MOD;
}
ll Pow(ll a , ll b , ll MOD)
{
ll res = 1;
while(b)
{
if((b & 1))res = Mul(res , a , MOD);
a = Mul(a , a , MOD);
b >>= 1;
}
return res;
}
ll Min(ll a , ll b)
{
if(a > b)return b;
return a;
}
ll Max(ll a , ll b)
{
if(a > b)return a;
return b;
}
ll Ceil(ll a , ll b)
{
if(a % b)return (a/b)+1;
return a/b;
}
/////////////////////
//VALS
ll n, m, q;
const ll maxn = 1100;
bool a[maxn][maxn];
ll b[maxn][maxn];
/////////////////////
//FUNCTIONS
bool chk(ll aa, ll bb)
{
if(aa == n-1 and bb == m-1)return 1;
if(b[aa][bb] > -1)return b[aa][bb];
if(a[aa][bb] == 1)return 0;
ll ans = 0;
if(aa+1 != n)
if(chk(aa+1,bb))ans = 1;
if(bb+1 != m)
if(chk(aa,bb+1))ans = 1;
return b[aa][bb] = ans;
}
/////////////////////
//SOLVE
void solve()
{
cin >> n >> m;
For(i,n)
For(j,m)
cin >> a[i][j];
cin >> q;
while(q--)
{
For(i,n)
For(j,m)
b[i][j] = -1;
ll aa,bb;
cin >> aa >> bb;
aa--;
bb--;
a[aa][bb] = 1;
if(chk(0,0))cout << 1 << endl;
else
{
cout << 0 << endl;
a[aa][bb] = 0;
}
}
}
/////////////////////
//MAIN
int main()
{
FAST;
ll t = 1;
// cin >> t;
while(t--)
{
solve();
}
}
/////////////////////
/*
ZZZZZZZ A M M IIIIIII N N
Z A A M M M M I NN N
Z A A M M M M I N N N
Z AAAAAAA M M M I N N N
Z A A M M I N N N
Z A A M M I N NN
ZZZZZZZ A A M M IIIIIII N N TREE
*/
Compilation message
furniture.cpp: In function 'bool chk(long long int, long long int)':
furniture.cpp:94:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
94 | return b[aa][bb] = ans;
| ~~~~~~~~~~^~~~~
furniture.cpp: In function 'void solve()':
furniture.cpp:19:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
19 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
furniture.cpp:102:2: note: in expansion of macro 'For'
102 | For(i,n)
| ^~~
furniture.cpp:19:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
19 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
furniture.cpp:103:3: note: in expansion of macro 'For'
103 | For(j,m)
| ^~~
furniture.cpp:19:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
19 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
furniture.cpp:110:4: note: in expansion of macro 'For'
110 | For(i,n)
| ^~~
furniture.cpp:19:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
19 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
| ^
furniture.cpp:111:5: note: in expansion of macro 'For'
111 | For(j,m)
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
4440 KB |
Output is correct |
2 |
Correct |
13 ms |
4444 KB |
Output is correct |
3 |
Correct |
54 ms |
4604 KB |
Output is correct |
4 |
Correct |
90 ms |
4952 KB |
Output is correct |
5 |
Correct |
99 ms |
4700 KB |
Output is correct |
6 |
Correct |
169 ms |
4736 KB |
Output is correct |
7 |
Correct |
67 ms |
4724 KB |
Output is correct |
8 |
Correct |
83 ms |
4700 KB |
Output is correct |
9 |
Correct |
200 ms |
4696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
4440 KB |
Output is correct |
2 |
Correct |
13 ms |
4444 KB |
Output is correct |
3 |
Correct |
54 ms |
4604 KB |
Output is correct |
4 |
Correct |
90 ms |
4952 KB |
Output is correct |
5 |
Correct |
99 ms |
4700 KB |
Output is correct |
6 |
Correct |
169 ms |
4736 KB |
Output is correct |
7 |
Correct |
67 ms |
4724 KB |
Output is correct |
8 |
Correct |
83 ms |
4700 KB |
Output is correct |
9 |
Correct |
200 ms |
4696 KB |
Output is correct |
10 |
Correct |
2818 ms |
5280 KB |
Output is correct |
11 |
Correct |
97 ms |
4720 KB |
Output is correct |
12 |
Execution timed out |
5014 ms |
12976 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |