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