fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/uP9Njy
language:
Python (cpython 2.7.16)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!