#include <bits/stdc++.h>
using namespace std;
int n, m, q, x, y, c[1005][1005], cnt[2005];
//cnt[i] stores number of nice paths through (x, y), such that x + y = i
//every nice path must pass through a point such that x + y = i for all i
bool p[1005][1005], vis[1005][1005]; //true if nice path passes through x, y
#define debug
bool dfs(int x, int y){
if (x < 1 || x > n || y < 1 || y > m) return false;
if (x == n && y == m){
p[x][y] = true;
return true;
}
if (c[x][y]) return false;
if (vis[x][y]) return p[x][y];
vis[x][y] = true;
bool b1 = dfs(x + 1, y);
bool b2 = dfs(x, y + 1);
p[x][y] = b1 || b2;
if (p[x][y]) ++cnt[x + y];
return p[x][y];
}
bool pos(int x, int y){
if (x < 1 || x > n || y < 1 || y > m) return false;
return p[x][y];
}
void u1(int x, int y){
if (x < 1 || x > n || y < 1 || y > m) return;
if (x == 1 && y == 1) return;
if (x == n && y == m) return;
if (!p[x][y]) return; //already no path to (x, y)
if (!(pos(x - 1, y) || pos(x, y - 1))){ //no path to (x, y)
p[x][y] = false;
--cnt[x + y];
}
else if (!(pos(x - 1, y) || pos(x, y - 1))){
p[x][y] = false;
--cnt[x + y];
}
u1(x + 1, y);
u1(x, y + 1);
}
void u2(int x, int y){
if (x < 1 || x > n || y < 1 || y > m) return;
if (x == 1 && y == 1) return;
if (x == n && y == m) return;
if (!p[x][y]) return; //already no path from (x, y) to (n, m)
if (!(pos(x + 1, y) || pos(x, y + 1))){ //no path from (x, y) to (n, m)
p[x][y] = false;
--cnt[x + y];
}
else if (!(pos(x - 1, y) || pos(x, y - 1))){
p[x][y] = false;
--cnt[x + y];
}
u2(x - 1, y);
u2(x, y - 1);
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
scanf("%d", &c[i][j]);
}
}
dfs(1, 1);
scanf("%d", &q);
for (int i = 0; i < q; ++i){
#ifdef debug
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
printf("%d ", p[i][j]);
}
printf("\n");
}
#endif // debug
scanf("%d%d", &x, &y);
if (!p[x][y]){
//no nice path passes through p[x][y], so just put
printf("1\n");
continue;
}
if (cnt[x + y] == 1){
//all nice paths must pass through (x, y), so cannot put
printf("0\n");
continue;
}
//more than 1 point which nice paths pass through with sum x + y, can put
printf("1\n");
p[x][y] = false;
--cnt[x + y];
u1(x + 1, y); //update towards (n, m)
u1(x, y + 1);
u2(x - 1, y); //update towards (1, 1)
u2(x, y - 1);
}
}
Compilation message
furniture.cpp: In function 'int main()':
furniture.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
67 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:70:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
70 | scanf("%d", &c[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
furniture.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
84 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5086 ms |
748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5086 ms |
748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
