232072026-01-16 17:11:50Erik_GepardCseppkőbarlang (45 pont)cpp17Accepted 45/4539ms6300 KiB
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<vector<int>> barlang;
vector<vector<vector<pair<int, int>>>> edges;
vector<vector<bool>> visited;
int barlangresz=0;

void dfs(int i, int j){
    visited[i][j]=true;
    for(pair<int, int> x : edges[i][j]){
        if(!visited[x.first][x.second]){
            dfs(x.first, x.second);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    barlang = vector<vector<int>>(n+1, vector<int> (m+1));
    edges = vector<vector<vector<pair<int, int>>>> (n+1, vector<vector<pair<int, int>>> (m+1));
    visited = vector<vector<bool>> (n+1, vector<bool> (m+1));
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin>>barlang[i][j];
            if(barlang[i][j]==0){
                visited[i][j]=true;
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(barlang[i][j]!=0){
                if(i>1&&barlang[i-1][j]>=barlang[i][j]){
                    edges[i][j].push_back({i-1, j});
                }
                if(j>1&&barlang[i][j-1]>=barlang[i][j]){
                    edges[i][j].push_back({i, j-1});
                }
                if(j<m&&barlang[i][j+1]>=barlang[i][j]){
                    edges[i][j].push_back({i, j+1});
                }
                if(i<n&&barlang[i+1][j]>=barlang[i][j]){
                    edges[i][j].push_back({i+1, j});
                }
            }
        }
    }
    vector<vector<int>> sorrend;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            sorrend.push_back({barlang[i][j], i, j});
        }
    }
    sort(sorrend.begin(), sorrend.end());
    vector<pair<int, int>> result;
    for(int i=0; i<sorrend.size(); i++){
        if(!visited[sorrend[i][1]][sorrend[i][2]]){
            result.push_back({sorrend[i][1], sorrend[i][2]});
            dfs(sorrend[i][1], sorrend[i][2]);
        }
    }
    cout<<result.size()<<"\n";
    for(pair<int, int> x : result){
        cout<<x.first<<" "<<x.second<<"\n";
    }

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base45/45
1Accepted0/01ms316 KiB
2Accepted0/01ms316 KiB
3Accepted1/11ms316 KiB
4Accepted1/11ms316 KiB
5Accepted2/232ms6300 KiB
6Accepted2/229ms5568 KiB
7Accepted2/230ms5560 KiB
8Accepted2/22ms316 KiB
9Accepted2/21ms564 KiB
10Accepted3/329ms5164 KiB
11Accepted3/339ms5804 KiB
12Accepted3/332ms4860 KiB
13Accepted3/328ms4844 KiB
14Accepted3/323ms4700 KiB
15Accepted3/332ms5348 KiB
16Accepted3/334ms5348 KiB
17Accepted3/335ms5524 KiB
18Accepted3/332ms5352 KiB
19Accepted3/329ms5276 KiB
20Accepted3/335ms5368 KiB