BOJ 2146ブリッジの作成
25883 ワード
BOJ 2146ブリッジの作成題です
島番号ごとに、周囲に川が流れている島の座標をキューに入れ、干拓日数を記録したdist配列の値を0に変更し、BFS検索で島の範囲を増やします.BFS中に他の島に遭遇した場合,これまでの距離(dist)値を加算することで解決できる.
#include <bits/stdc++.h>
using namespace std;
int dist[101][101];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
bool vis[101][101];
int graph[101][101];
int n;
int islandNum = 0;
int main() {
cout.sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 0; i < n; i++) {
fill(dist[i], dist[i] + n, -1);
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> graph[i][j];
}
}
queue<pair<int, int>> Q1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++){
if(!vis[i][j] && graph[i][j] == 1) {
islandNum++;
Q1.push({i, j});
vis[i][j] = true; graph[i][j] = islandNum;
while(!Q1.empty()){
auto cur = Q1.front(); Q1.pop();
for(int i = 0; i < n; i++){
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if(vis[nx][ny]) continue;
if(graph[nx][ny] == 0) continue;
Q1.push({nx, ny});
vis[nx][ny] = true;
graph[nx][ny] = islandNum;
}
}
}
}
}
queue<pair<int, int>> Q2;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++){
if(graph[i][j] >= 1) {
for(int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if(graph[nx][ny] == 0) {
dist[i][j] = 0;
Q2.push({i, j});
break;
}
}
}
}
}
int ans = 9999;
while(!Q2.empty()) {
auto cur = Q2.front(); Q2.pop();
for(int i = 0; i < 4; i++) {
int nx = cur.first + dx[i];
int ny = cur.second + dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if(graph[cur.first][cur.second] == graph[nx][ny]) continue;
if(graph[nx][ny] != graph[cur.first][cur.second] && graph[nx][ny] != 0) {
int cost = dist[nx][ny] + dist[cur.first][cur.second];
ans = min(cost, ans);
}
if(dist[nx][ny] >= 0) continue;
Q2.push({nx, ny});
dist[nx][ny] = dist[cur.first][cur.second] + 1;
graph[nx][ny] = graph[cur.first][cur.second];
}
}
cout << ans;
return 0;
}
BFSではキューに入れたり取り出したりするのは私の考えと違うかもしれないので、最大値と最小値を出力する過程で、できるだけBFS過程が終わった後に出力します.島番号ごとに、周囲に川が流れている島の座標をキューに入れ、干拓日数を記録したdist配列の値を0に変更し、BFS検索で島の範囲を増やします.BFS中に他の島に遭遇した場合,これまでの距離(dist)値を加算することで解決できる.
Reference
この問題について(BOJ 2146ブリッジの作成), 我々は、より多くの情報をここで見つけました https://velog.io/@januaryone/BFS-문제-모음계속-수정テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol