17472ブリッジ2

これは非常に複雑なシミュレーション問題である.複数のアルゴリズムを練習するのに適しています.

質問リンク

https://www.acmicpc.net/problem/17472

に答える

まずそれぞれの島を区別しなければならないので、島番号を付けなければなりません.
アクセスされていない島に遭遇した場合、bfsを介して各島の数字にnumを加算し、numの1番目の島の情報をベクトル配列に格納することができる.
次いで、島と島との距離、すなわちコストを表す2次元disアレイを初期化する.初期化値は任意の大数101である.その後、すべての島が接続されているか否かを接続島のコスト値で判断するため、十分な値に初期化する必要がある.
その後、島から島までの長さを求めるため、現在の島から上下左右に移動する島を探索するため、dfsを回ります.
今の島からずっと一方向に進むと、島を見つけることができます.
このような島が存在する場合、その島のコストが確認され、コストが既存のコストより小さい場合、disアレイが更新される.
座標からずれるか、コストが2未満の場合は、直接戻ります.
島と島の間のすべてのコストがすでに求められている場合、クルーズアルゴリズムによって最短距離が求められる.
島と島の間のエッジ情報を含むEdgeクラスを宣言し、getParent、unionParent、find関数を実装してunion-findを適用します.
Edgeシナリオvを宣言し、Edgeの情報を含む.
ループ文にノードとコスト値を格納します.
このときcostはdisアレイの値である.
値を保存した後、costをsortで昇順に並べ替えます.
次にクルーズアルゴリズムを適用し,コストの最小エッジから接続を開始する.
費用の合計ansが101以上であれば、未接続の島が存在することを示し(接続されている場合、dfsを回転すると101よりずっと小さい数に更新)、出力−1.
そうでなければansを出力すればいいです.

C++コード

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define endl '\n'

using namespace std;

int arr[10][10];
bool visit[10][10];
int root[6];
int N, M;
vector<pair<int,int>> land[6];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int dis[6][6];

int getParent(int x){
    if(root[x] == x) return x;
    return root[x] = getParent(root[x]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a < b) root[b] = a;
    else root[a] = b;
}

bool find(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    return false;
}

// 섬을 노드로 섬사이의 거리를 edge로
class Edge{
public:
    int node[2];
    int cost;
    Edge(int a, int b, int cost){
        this->node[0] = a;
        this->node[1] = b;
        this->cost = cost;
    }
    bool operator <(Edge &edge){
        return this->cost < edge.cost;
    }
};

void bfs(int i, int j, int num){
    queue<pair<int,int>> q;
    q.push({i,j});
    visit[i][j] == true;
    arr[i][j] += num;
    while(!q.empty()){
        pair<int,int> now = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int nx = now.first+dx[i], ny = now.second+dy[i];
            if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
            if(!visit[nx][ny] && arr[nx][ny] == 1){
                visit[nx][ny] = true;
                arr[nx][ny] += num;
                land[num].push_back({nx,ny});
                q.push({nx,ny});
            }
        }
    }
}

void dfs(pair<int, int> now, int n, int start, int cost){
    // n 탐색할 방향 des 목적지 섬
    int nx = now.first + dx[n];
    int ny = now.second + dy[n];
    if(nx<0 || nx>=N || ny<0 || ny>=M) return;
    if(arr[nx][ny] != 0){
        if(arr[nx][ny] == start || cost < 2) return;
        if(dis[start-1][arr[nx][ny]-1]>cost){
            dis[start-1][arr[nx][ny]-1] = cost;
            dis[arr[nx][ny]-1][start-1] = cost;
        }
        return;
    }
    else
    	dfs(make_pair(nx, ny), n, start, cost+1);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>N>>M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin>>arr[i][j];
        }
    }
    // 섬에 번호 붙여줌
    int num = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(arr[i][j] == 1 && !visit[i][j]){
                land[num].push_back({i,j});
                bfs(i, j, num);
                num++;
            }
        }
    }
    // dis 초기화
    for(int i=0; i<num; i++){
        for(int j=0; j<num; j++){
            dis[i][j] = 101;
        }
    }
    // 섬에서 섬끼리 길이 구함
    for(int i=0; i<num; i++){
        for(int j=0; j<land[i].size(); j++){
            // 자기 자신보다 번호가 작은 섬까지의 최적 거리는 이미 구해져있음
            for(int des=i+1; des<num; des++){
                for(int n=0; n<4; n++){
                    dfs(land[i][j], n, i+1, 0);
                }
            }
        }
    }
    // root 초기화
    for(int i=0; i<num; i++){
        root[i] = i;
    }
    vector<Edge> v; // 노드 정보 저장
    // Edge 정보 저장
    for(int i=0; i<num; i++){
        for(int j=i+1; j<num; j++){
            v.push_back(Edge(i,j,dis[i][j]));
        }
    }
    sort(v.begin(), v.end());
    int ans = 0;
    for(int i=0; i<num; i++){
        if(!find(v[i].node[0], v[i].node[1])){
            ans += v[i].cost;
            unionParent(v[i].node[0], v[i].node[1]);
        }
    }
    if(ans >= 101)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    
    return 0;
}