fork download
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #include <algorithm>
  3. #include <string>
  4. #include <set>
  5. #include <map>
  6. #include <vector>
  7. #include <queue>
  8. #include <iostream>
  9. #include <iterator>
  10. #include <cmath>
  11. #include <cstdio>
  12. #include <cstdlib>
  13. #include <sstream>
  14. #include <fstream>
  15. #include <ctime>
  16. #include <cstring>
  17. #include <functional>
  18. #include <bitset>
  19. #pragma comment(linker, "/STACK:266777216")
  20. using namespace std;
  21. #define pb push_back
  22. #define ppb pop_back
  23. #define pi 3.1415926535897932384626433832795028841971
  24. #define mp make_pair
  25. #define x first
  26. #define y second
  27. #define pii pair<int,int>
  28. #define pdd pair<double,double>
  29. #define INF 1000000000
  30. #define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
  31. #define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
  32. #define all(c) (c).begin(), (c).end()
  33. #define SORT(c) sort(all(c))
  34. #define rep(i,n) FOR(i,1,(n))
  35. #define rept(i,n) FOR(i,0,(n)-1)
  36. #define L(s) (int)((s).size())
  37. #define C(a) memset((a),0,sizeof(a))
  38. #define VI vector <int>
  39. #define ll long long
  40.  
  41. const int di[] = { 0, 1, 0, -1 };
  42. const int dj[] = { 1, 0, -1, 0 };
  43.  
  44. int a, b, c, d, n, m, k;
  45. char mas[2002][2002];
  46. int cs[2002][2002], cs2[4][2002][2002];
  47. int hor[2002][2002], ver[2002][2002];
  48. bool used[2002][2002];
  49.  
  50. pii sof[4];
  51. pii q[4000002];
  52. void bfs(int bi, int bj) {
  53. int a = 0, b = 0;
  54. q[b++] = mp(bi, bj);
  55. used[bi][bj] = 1;
  56. while (a < b) {
  57. int ci = q[a].x;
  58. int cj = q[a++].y;
  59. sof[0] = min(sof[0], pii(ci, cj));
  60. sof[1] = min(sof[1], pii(cj, ci));
  61. sof[2] = min(sof[2], pii(-ci, -cj));
  62. sof[3] = min(sof[3], pii(-cj, -ci));
  63. rept(i, 4) {
  64. int ni = ci + di[i];
  65. int nj = cj + dj[i];
  66. if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
  67. if (used[ni][nj] || mas[ni][nj] != mas[ci][cj]) continue;
  68. used[ni][nj] = 1;
  69. q[b++] = mp(ni, nj);
  70. }
  71. }
  72. }
  73. inline int sum(int x, int y) {
  74. if (x < 0 || y < 0) return 0;
  75. return cs[x][y];
  76. }
  77. inline int sum(int x1, int y1, int x2, int y2) {
  78. return sum(x2, y2) - sum(x1 - 1, y2) - sum(x2, y1 - 1) + sum(x1 - 1, y1 - 1);
  79. }
  80. inline int sum2(int t, int x, int y) {
  81. if (x < 0 || y < 0) return 0;
  82. return cs2[t][x][y];
  83. }
  84. inline int sum2(int t, int x1, int y1, int x2, int y2) {
  85. return sum2(t, x2, y2) - sum2(t, x1 - 1, y2) - sum2(t, x2, y1 - 1) + sum2(t, x1 - 1, y1 - 1);
  86. }
  87. inline int solve(int r1, int c1, int r2, int c2) {
  88. int t = sum(r1, c1, r2, c2);
  89. if (!t || t == (r2 - r1 + 1) * (c2 - c1 + 1)) return 1;
  90.  
  91. if (r1 == r2) {
  92. if (hor[r1][c2] - hor[r1][c1] == 1) return 2; else
  93. return 0;
  94. }
  95. if (c1 == c2) {
  96. if (ver[r2][c1] - ver[r1][c1] == 1) return 2; else
  97. return 0;
  98. }
  99.  
  100. int cnt = hor[r1][c2] - hor[r1][c1] + 1;
  101. cnt += hor[r2][c2] - hor[r2][c1];
  102. cnt += ver[r2][c1] - ver[r1][c1];
  103. cnt += ver[r2][c2] - ver[r1][c2] - 1;
  104.  
  105. if (cnt > 2) return 0;
  106.  
  107. if (cnt <= 1) {
  108. if (sum2(0, r1 + 1, c1 + 1, r2 - 1, c2 - 1) <= 1) return 2; else
  109. return 0;
  110. }
  111.  
  112. rept(i, 4) {
  113. if (!sum2(i, r1 + 1, c1 + 1, r2 - 1, c2 - 1)) return 2;
  114. }
  115. return 0;
  116. }
  117. int main() {
  118. //freopen("input.txt", "r", stdin);
  119. //freopen("output.txt", "w", stdout);
  120.  
  121. gets(mas[0]);
  122. sscanf(mas[0], "%d%d", &n, &m);
  123. rept(i, n) {
  124. gets(mas[i]);
  125. rept(j, m) {
  126. cs[i][j] = mas[i][j] - '0';
  127. if (!i && !j); else
  128. if (!j) cs[i][j] += cs[i - 1][j]; else
  129. if (!i) cs[i][j] += cs[i][j - 1]; else
  130. cs[i][j] += cs[i - 1][j] + cs[i][j - 1] - cs[i - 1][j - 1];
  131. }
  132. }
  133.  
  134. rept(i, n) {
  135. rept(j, m) {
  136. hor[i][j] = 0;
  137. if (j && mas[i][j] != mas[i][j - 1]) ++hor[i][j];
  138. if (j) hor[i][j] += hor[i][j - 1];
  139.  
  140. ver[i][j] = 0;
  141. if (i && mas[i - 1][j] != mas[i][j]) ++ver[i][j];
  142. if (i) ver[i][j] += ver[i - 1][j];
  143. }
  144. }
  145.  
  146. C(used);
  147. rept(i, n) {
  148. rept(j, m) {
  149. if (!used[i][j]) {
  150. sof[0] = sof[1] = sof[2] = sof[3] = mp(INF, INF);
  151. bfs(i, j);
  152. cs2[0][sof[0].x][sof[0].y] = 1;
  153. cs2[1][sof[1].y][sof[1].x] = 1;
  154. cs2[2][-sof[2].x][-sof[2].y] = 1;
  155. cs2[3][-sof[3].y][-sof[3].x] = 1;
  156. }
  157. }
  158. }
  159.  
  160. rept(z, 4) {
  161. rept(i, n) {
  162. rept(j, m) {
  163. if (!i && !j) continue;
  164. if (!i) cs2[z][i][j] += cs2[z][i][j - 1]; else
  165. if (!j) cs2[z][i][j] += cs2[z][i - 1][j]; else
  166. cs2[z][i][j] += cs2[z][i - 1][j] + cs2[z][i][j - 1] - cs2[z][i - 1][j - 1];
  167. }
  168. }
  169. }
  170.  
  171. scanf("%d", &k);
  172. rept(i, k) {
  173. int r1, c1, r2, c2;
  174. scanf("%d%d%d%d", &r1, &c1, &r2, &c2); --r1; --c1; --r2; --c2;
  175. printf("%d\n", solve(r1, c1, r2, c2));
  176. }
  177. }
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
compilation info
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/lib/python2.7/py_compile.py", line 117, in compile
    raise py_exc
py_compile.PyCompileError: SyntaxError: ('invalid syntax', ('prog.py', 20, 15, 'using namespace std;\n'))

stdout
Standard output is empty