Advertisement
Guest User

Untitled

a guest
Feb 28th, 2020
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, m, k;
  6.  
  7. #define pb push_back
  8.  
  9. int get_id (pair <int, int> x)
  10. {
  11. return x.second + (x.first - 1) * m;
  12. }
  13.  
  14. pair <int, int> get_pair (int x)
  15. {
  16. return {(x - 1) / m + 1, (x - 1) % m + 1};
  17. }
  18.  
  19. const int N = 150;
  20.  
  21. bool viz[1 + N][1 + N];
  22. int key[1 + N][1 + N];
  23.  
  24. bool open[1 + N * N];
  25. vector <int> rooms[1 + N * N];
  26.  
  27. int dx[4] = {0, -1, 0, 1};
  28. int dy[4] = {-1, 0, 1, 0};
  29.  
  30. bool inside (pair <int, int> x)
  31. {
  32. return 1 <= x.first && x.first <= n && 1 <= x.second && x.second <= m;
  33. }
  34.  
  35. int main () {
  36.  
  37. freopen ("castel.in", "r", stdin);
  38. freopen ("castel.out", "w", stdout);
  39.  
  40. ios::sync_with_stdio (false);
  41. cin.tie (0);
  42. cout.tie (0);
  43.  
  44. cin >> n >> m >> k;
  45. for (int i = 1; i <= n; i++)
  46. {
  47. for (int j = 1; j <= m; j++)
  48. cin >> key[i][j];
  49. }
  50.  
  51. queue <int> q;
  52. q.push (k);
  53.  
  54. int ans = 0;
  55. auto c = get_pair (k);
  56. viz[c.first][c.second] = true;
  57.  
  58. while (q.size ())
  59. {
  60. int node = q.front ();
  61. q.pop (); ans++;
  62.  
  63. auto c = get_pair (node);
  64.  
  65. if (!open[node])
  66. {
  67. open[node] = true;
  68. for (auto x : rooms[node])
  69. q.push (x);
  70. }
  71.  
  72. for (int dir = 0; dir < 4; dir++)
  73. {
  74. pair <int, int> nc = {c.first + dx[dir], c.second + dy[dir]};
  75. if (inside (nc) && !viz[nc.first][nc.second])
  76. {
  77. viz[nc.first][nc.second] = true;
  78. int val = key[nc.first][nc.second];
  79.  
  80. if (open[val])
  81. q.push (get_id (nc));
  82. else
  83. rooms[val].pb (get_id (nc));
  84. }
  85. }
  86. }
  87. cout << ans << "\n";
  88. return 0;
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement