다리만들기

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>

using namespace std;

int n;
int map[100][100];
int mapping[100][100];
bool d[100][100];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int ans = 100000000;


void bfs(int x, int y, int value){

    queue<pair<int,int>> q;
    q.push({x,y});
    map[x][y] = 0;
    d[x][y] = true;
    while(!q.empty()){
        x = q.front().first; y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x+dx[i]; int ny = y+dy[i];
            if(nx >=0 && nx < n && ny>= 0 && ny<n){
                if(mapping[nx][ny] != value){
                    if(d[nx][ny] == false){
                        if(mapping[nx][ny] != 0 && mapping[nx][ny] != value){
                            ans = ans > map[x][y] ? map[x][y] : ans;
                        }
                        map[nx][ny] = map[x][y] + 1;
                        d[nx][ny] = true;
                        q.push({nx,ny});
                    }
                }
            }
        }
    }

}

void make_map(int x, int y, int value){
    queue<pair<int, int>> q;
    q.push({x,y});
    mapping[x][y] = value;
    d[x][y] = true;
    while(!q.empty()){
        x = q.front().first;  y = q.front().second;
        q.pop();
        for(int i = 0; i < 4; i++){
            int nx = x+dx[i]; int ny = y+dy[i];
            if(nx >=0 && nx < n && ny>= 0 && ny<n){
                if(map[nx][ny] == 1){
                    if(d[nx][ny] == false){
                        mapping[nx][ny] = value;
                        d[nx][ny] = true;
                        q.push({nx,ny});
                    }
                }
            }
        }
    }
}

int main(){
    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            scanf("%d", &map[i][j]);
        }
    }

    int value = 1;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(map[i][j] == 1){
                if(d[i][j] == false){
                    make_map(i,j, value);
                    value++;
                }
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(mapping[i][j] != 0) {
                memset(d, false, sizeof(d));
                memset(map, 0, sizeof(d));
                bfs(i, j, mapping[i][j]);
            }
        }
    }
    printf("%d\n", ans);

}