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
stdin
Standard input is empty
stdout
Standard output is empty