Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- string bin[16];
- int id = 0;
- const int maxN = 1010;
- int n, m;
- vector<pair<int,int>> adj[maxN][maxN];
- bool visited[maxN][maxN];
- void get_bin (int x,string s) {
- if ((int) s.size() == x) {
- bin[id++] = s;
- return;
- }
- get_bin(x,s + '0');
- get_bin(x,s + '1');
- }
- int cnt = 0;
- void dfs (int i,int j) {
- cnt++;
- visited[i][j] = true;
- for (pair<int,int> child : adj[i][j]) {
- if (visited[child.first][child.second] == false) {
- dfs(child.first,child.second);
- }
- }
- }
- int main () {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- get_bin(4,"");
- cin >> n >> m;
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= m; ++j) {
- int x;
- cin >> x;
- string s = bin[x];
- //up,right,down,left
- if (s[0] == '0') {
- if (i - 1 >= 1) {
- adj[i][j].push_back(make_pair(i - 1,j)); // up
- }
- }
- if (s[1] == '0') {
- if (j + 1 <= m) {
- adj[i][j].push_back(make_pair(i, j + 1)); // right
- }
- }
- if (s[2] == '0') {
- if (i + 1 <= n) {
- adj[i][j].push_back(make_pair(i + 1,j)); //down
- }
- }
- if (s[3] == '0') {
- if (j - 1 >= 1) {
- adj[i][j].push_back(make_pair(i,j - 1)); // left
- }
- }
- }
- }
- vector<int> res;
- for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= m; ++j) {
- if (visited[i][j] == false) {
- cnt = 0;
- dfs(i,j);
- res.push_back(cnt);
- }
- }
- }
- sort(res.rbegin(),res.rend());
- for (int i = 0; i < (int) res.size(); ++i) {
- cout << res[i] << ' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement