fork(6) 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[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
stdin
Standard input is empty
stdout
Standard output is empty