fork(5) download 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <cstdio>
  3. #include <vector>
  4. #include <queue>
  5. #include <cstring>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. const int inf = 1e9;
  10.  
  11. int dist[55][55], ad[55][55], n, x, y, ex, ey;
  12. int v[55][55];
  13. int dx[] = { -1, 1, 0, 0 };
  14. int dy[] = { 0, 0, -1, 1 };
  15.  
  16. struct ii {
  17. 	int x, y;
  18. 	ii(int a, int b) {
  19. 		x = a, y = b;
  20. 	}
  21. };
  22.  
  23. bool valid(int nx, int ny) {
  24. 	return nx >= 0 && ny >= 0 && nx < n && ny < n;
  25. }
  26.  
  27. bool checkBit(int mask, int bit) {
  28. 	return (mask & (1 << bit));
  29. }
  30.  
  31. bool bfs(int x, int y, int mask) {
  32. 	if (!checkBit(mask, ad[x][y])) {
  33. 		return false;
  34. 	}
  35.  
  36. 	queue <ii> q; q.push(ii(x, y));
  37. 	v[x][y] = mask;
  38.  
  39. 	while (!q.empty()) {
  40. 		ii curr = q.front(); q.pop();
  41. 		int X = curr.x, Y = curr.y;
  42. 		if (X == ex && Y == ey)
  43. 			return true;
  44.  
  45. 		for (int i = 0; i < 4; i++) {
  46. 			int nx = X + dx[i], ny = Y + dy[i];
  47. 			if (valid(nx, ny) && checkBit(mask, ad[nx][ny])) {
  48. 				if (v[nx][ny] != mask) {
  49. 					v[nx][ny] = mask;
  50. 					q.push(ii(nx, ny));
  51. 				}
  52. 			}
  53. 		}
  54. 	}
  55.  
  56. 	return false;
  57. }
  58.  
  59. #define gc getchar_unlocked
  60. void s(int &x) {
  61. 	register int c = gc();
  62. 	x = 0;
  63. 	for (; (c<48 || c>57); c = gc());
  64. 	for (; c > 47 && c < 58; c = gc()) { x = (x << 1) + (x << 3) + c - 48; }
  65. }
  66.  
  67. int main(void) {
  68. 	//freopen("in.txt", "r", stdin);
  69. 	int t; s(t);
  70. 	while (t--) {
  71. 		s(n);
  72.  
  73. 		for (int i = 0; i < n; i++) {
  74. 			for (int j = 0; j < n; j++) {
  75. 				s(ad[i][j]);
  76. 			}
  77. 		}
  78.  
  79. 		s(x), s(y), s(ex), s(ey);
  80.  
  81. 		memset(dist, 0x3f, sizeof dist);
  82. 		memset(v, (1 << 11), sizeof v);
  83.  
  84. 		int ans = inf;
  85. 		for (int mask = 1, lim = (1 << 10); mask < lim; ++mask) {
  86. 			if (bfs(x, y, mask)) {
  87. 				int bit_count = 0;
  88. 				for (int bit = 0; bit < 10; ++bit) {
  89. 					if (checkBit(mask, bit)) {
  90. 						++bit_count;
  91. 					}
  92. 				}
  93.  
  94. 				ans = (ans > bit_count? bit_count: ans);
  95. 			}
  96. 		}
  97.  
  98. 		printf("%d\n", ans);
  99. 	}
  100. }
Time limit exceeded #stdin #stdout 5s 3376KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/QC3vmQ
language:
C++ (gcc 8.3)
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!