Advertisement
newb_ie

1

Oct 20th, 2021
234
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.58 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. string bin[16];
  4. int id = 0;
  5.  
  6. const int maxN = 1010;
  7. int n, m;
  8. vector<pair<int,int>> adj[maxN][maxN];
  9. bool visited[maxN][maxN];
  10.  
  11. void get_bin (int x,string s) {
  12. if ((int) s.size() == x) {
  13. bin[id++] = s;
  14. return;
  15. }
  16. get_bin(x,s + '0');
  17. get_bin(x,s + '1');
  18. }
  19.  
  20. int cnt = 0;
  21.  
  22. void dfs (int i,int j) {
  23. cnt++;
  24. visited[i][j] = true;
  25. for (pair<int,int> child : adj[i][j]) {
  26. if (visited[child.first][child.second] == false) {
  27. dfs(child.first,child.second);
  28. }
  29. }
  30. }
  31.  
  32. int main () {
  33. ios::sync_with_stdio(false);
  34. cin.tie(nullptr);
  35. cout.tie(nullptr);
  36. get_bin(4,"");
  37. cin >> n >> m;
  38. for (int i = 1; i <= n; ++i) {
  39. for (int j = 1; j <= m; ++j) {
  40. int x;
  41. cin >> x;
  42. string s = bin[x];
  43. //up,right,down,left
  44. if (s[0] == '0') {
  45. if (i - 1 >= 1) {
  46. adj[i][j].push_back(make_pair(i - 1,j)); // up
  47. }
  48. }
  49. if (s[1] == '0') {
  50. if (j + 1 <= m) {
  51. adj[i][j].push_back(make_pair(i, j + 1)); // right
  52. }
  53. }
  54. if (s[2] == '0') {
  55. if (i + 1 <= n) {
  56. adj[i][j].push_back(make_pair(i + 1,j)); //down
  57. }
  58. }
  59. if (s[3] == '0') {
  60. if (j - 1 >= 1) {
  61. adj[i][j].push_back(make_pair(i,j - 1)); // left
  62. }
  63. }
  64. }
  65. }
  66. vector<int> res;
  67. for (int i = 1; i <= n; ++i) {
  68. for (int j = 1; j <= m; ++j) {
  69. if (visited[i][j] == false) {
  70. cnt = 0;
  71. dfs(i,j);
  72. res.push_back(cnt);
  73. }
  74. }
  75. }
  76. sort(res.rbegin(),res.rend());
  77. for (int i = 0; i < (int) res.size(); ++i) {
  78. cout << res[i] << ' ';
  79. }
  80. }
  81.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement