白峻3197号:白鳥湖
25623 ワード
白鳥の湖
白峻3197号:白鳥湖
アイデア
文明問題と全く同じだ.水は文明に代わって伝播する.伝播の度に左右に水があることを確認するとユニオンが年度を変えるとfind実は一年ではなく一日です.
初めて水と白鳥をドキュメンタリーに入れ、上下左右に水や白鳥があればユニオンを作ってあげます.
コード#コード#
#include <bits/stdc++.h>
using namespace std;
const int dy[4] = {1, -1, 0, 0};
const int dx[4] = {0, 0, 1, -1};
int N, M;
int arr[2000][2000];
int p[4000000];
vector<pair<int, int>> v;
vector<pair<int, int>> sv;
int find(int n) {
if (p[n] < 0) return n;
return p[n] = find(p[n]);
}
void Union(int n1, int n2) {
n1 = find(n1);
n2 = find(n2);
if (n1 == n2) return;
p[n1] += p[n2];
p[n2] = n1;
}
bool check() {
int np = find(M*v[0].first+v[0].second);
for (auto p : v) {
if (find(M*p.first+p.second) != np) return false;
}
return true;
}
int bfs() {
queue<pair<int, int>> q;
for (auto p : sv) {
q.push({p.first, p.second});
for (int i = 0; i < 4; i++) {
int ny = p.first + dy[i];
int nx = p.second + dx[i];
if (ny >= N || ny < 0 || nx >= M || nx < 0) continue;
if (arr[ny][nx] != 0) Union(M*ny+nx, M*p.first+p.second);
}
}
if (check()) return 0;
int year = 1;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
int y = cur.first;
int x = cur.second;
if (year != arr[y][x]) {
if (check()) return year;
year++;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= N || ny < 0 || nx >= M || nx < 0) continue;
if (arr[ny][nx] != 0) continue;
arr[ny][nx] = arr[y][x] + 1;
for (int j = 0; j < 4; j++) {
int nny = ny + dy[j];
int nnx = nx + dx[j];
if (nny >= N || nny < 0 || nnx >= M || nnx < 0) continue;
if (arr[nny][nnx] != 0) {
Union(M*nny+nnx, M*ny+nx);
}
}
q.push({ny, nx});
}
}
return year;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
char x;
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> x;
if (x == 'L') {
arr[i][j] = 1;
v.push_back({i, j});
sv.push_back({i, j});
}
else if (x == 'X') {
arr[i][j] = 0;
}
else if (x == '.') {
arr[i][j] = 1;
sv.push_back({i, j});
}
}
}
memset(p, -1, sizeof(p));
cout << bfs();
return 0;
}
おしゃべり
この正解率は19分みんながbfs dfsを作っている間にタイムアウトしました
Reference
この問題について(白峻3197号:白鳥湖), 我々は、より多くの情報をここで見つけました
https://velog.io/@ks1ksi/백준-3197번-백조의-호수
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
#include <bits/stdc++.h>
using namespace std;
const int dy[4] = {1, -1, 0, 0};
const int dx[4] = {0, 0, 1, -1};
int N, M;
int arr[2000][2000];
int p[4000000];
vector<pair<int, int>> v;
vector<pair<int, int>> sv;
int find(int n) {
if (p[n] < 0) return n;
return p[n] = find(p[n]);
}
void Union(int n1, int n2) {
n1 = find(n1);
n2 = find(n2);
if (n1 == n2) return;
p[n1] += p[n2];
p[n2] = n1;
}
bool check() {
int np = find(M*v[0].first+v[0].second);
for (auto p : v) {
if (find(M*p.first+p.second) != np) return false;
}
return true;
}
int bfs() {
queue<pair<int, int>> q;
for (auto p : sv) {
q.push({p.first, p.second});
for (int i = 0; i < 4; i++) {
int ny = p.first + dy[i];
int nx = p.second + dx[i];
if (ny >= N || ny < 0 || nx >= M || nx < 0) continue;
if (arr[ny][nx] != 0) Union(M*ny+nx, M*p.first+p.second);
}
}
if (check()) return 0;
int year = 1;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
int y = cur.first;
int x = cur.second;
if (year != arr[y][x]) {
if (check()) return year;
year++;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= N || ny < 0 || nx >= M || nx < 0) continue;
if (arr[ny][nx] != 0) continue;
arr[ny][nx] = arr[y][x] + 1;
for (int j = 0; j < 4; j++) {
int nny = ny + dy[j];
int nnx = nx + dx[j];
if (nny >= N || nny < 0 || nnx >= M || nnx < 0) continue;
if (arr[nny][nnx] != 0) {
Union(M*nny+nnx, M*ny+nx);
}
}
q.push({ny, nx});
}
}
return year;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
char x;
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> x;
if (x == 'L') {
arr[i][j] = 1;
v.push_back({i, j});
sv.push_back({i, j});
}
else if (x == 'X') {
arr[i][j] = 0;
}
else if (x == '.') {
arr[i][j] = 1;
sv.push_back({i, j});
}
}
}
memset(p, -1, sizeof(p));
cout << bfs();
return 0;
}
Reference
この問題について(白峻3197号:白鳥湖), 我々は、より多くの情報をここで見つけました https://velog.io/@ks1ksi/백준-3197번-백조의-호수テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol