白駿16234号人口移転(C++)
4040 ワード
お久しぶりです.決してずっと遊んでいるわけではありません.
途中でコロナが発生し、2週間ほど苦労しましたが、問題はいつも解決しています.
特に質問はないようですが、ブログで発表します.
でもさっきはこの一ヶ月で何人かいたような….うんうん...
要するに、今日発表される問題は人口移転のグラフ探索問題である.
普段のペクジュンシミュレーションタグの問題は私にとって他の同じレベルの問題よりずっと難しいので、この問題を克服するために解いてみました.
まず、白駿のもう一つのグラフ探索問題番号のみのアイデアを持ってきて、bfsを行うたびに[y][x]記録にアクセスする数字を増やし、人口を更新します.
ex.(1,1)でナビゲーション時に[1][1]=1にアクセスすると、(1,2)でナビゲーション時に[1][2]=2にアクセスする
アクセスされていないポイントをキューに入れ、その周囲のポイントが人口移動条件を満たす場合、その値をvalに加算し、cnt個数を増やすようにbfsを実行します.
キューが要求されるまで、[y][x]の値にアクセスして同じ頂点の値を変更します.
すべてのポイントでbfsを実行すると、アクセスした配列が0に初期化され、グラフィックブラウズが再開されます.
人口が移動できないまで図形を繰り返し探索するため,movecntという変数を用いてそれを検査し脱出することができる.
時間制限は2秒マップの幅が50*50しかないのでTLEは受けないと思いますが...
しかし、時間の複雑さがどれほどなのかは分からない.
全地図閲覧回数の最大値が全bfsであれば、両国ごとに人口の流れがあると仮定すると、2分の1のbfsごとに回数が減少するので、logn*n上の地図全体は50*50で、4方向です...n*2logn他の人は草を探しても時間の複雑さには言及しなかった.
ブログを书くたびに、本当に私だけを见るために书いた文章のような気がします.
他の人を見ると可読性も良く理解も良いのですが、私なら私を見たら理解できません….なんだ.多用すれば少しは良くなるでしょう.ううう
途中でコロナが発生し、2週間ほど苦労しましたが、問題はいつも解決しています.
特に質問はないようですが、ブログで発表します.
でもさっきはこの一ヶ月で何人かいたような….うんうん...
要するに、今日発表される問題は人口移転のグラフ探索問題である.
普段のペクジュンシミュレーションタグの問題は私にとって他の同じレベルの問題よりずっと難しいので、この問題を克服するために解いてみました.
문제링크
https://www.acmicpc.net/problem/16234 설명
これは人口が移動できないまで地図全体を探索し修正する問題である.まず、白駿のもう一つのグラフ探索問題番号のみのアイデアを持ってきて、bfsを行うたびに[y][x]記録にアクセスする数字を増やし、人口を更新します.
ex.(1,1)でナビゲーション時に[1][1]=1にアクセスすると、(1,2)でナビゲーション時に[1][2]=2にアクセスする
アクセスされていないポイントをキューに入れ、その周囲のポイントが人口移動条件を満たす場合、その値をvalに加算し、cnt個数を増やすようにbfsを実行します.
キューが要求されるまで、[y][x]の値にアクセスして同じ頂点の値を変更します.
すべてのポイントでbfsを実行すると、アクセスした配列が0に初期化され、グラフィックブラウズが再開されます.
人口が移動できないまで図形を繰り返し探索するため,movecntという変数を用いてそれを検査し脱出することができる.
時間制限は2秒マップの幅が50*50しかないのでTLEは受けないと思いますが...
しかし、時間の複雑さがどれほどなのかは分からない.
全地図閲覧回数の最大値が全bfsであれば、両国ごとに人口の流れがあると仮定すると、2分の1のbfsごとに回数が減少するので、logn*n上の地図全体は50*50で、4方向です...n*2logn他の人は草を探しても時間の複雑さには言及しなかった.
ブログを书くたびに、本当に私だけを见るために书いた文章のような気がします.
他の人を見ると可読性も良く理解も良いのですが、私なら私を見たら理解できません….なんだ.多用すれば少しは良くなるでしょう.ううう
코드
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
int n, l, r, ans = 0;
int map[51][51], visited[51][51], dir[4][2] = { {-1, 0},{0, 1},{1, 0},{0, -1} };
struct node {
int y, x;
};
void input()
{
cin >> n >> l >> r;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> map[i][j];
}
void resetvisited()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
visited[i][j] = 0;
}
void solution()
{
while (1)
{
int seq = 1;
int movecnt = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (visited[i][j]) // 이미 처리한 점이라면 넘김
continue;
visited[i][j] = seq;
queue<node> q;
q.push({ i, j });
int val = map[i][j]; // 전체값을 구하기 위해
int cnt = 1; // 개수를 구하기 위해
while (!q.empty())
{
int y = q.front().y;
int x = q.front().x;
q.pop();
for (int k = 0; k < 4; k++)
{
int ny = y + dir[k][0];
int nx = x + dir[k][1];
if (ny <= 0 || ny > n || nx <= 0 || nx > n || visited[ny][nx]) // 범위 벗어났거나 이미 방문했을 시 넘김
continue;
int dif = abs(map[y][x] - map[ny][nx]);
if (dif >= l && dif <= r) // 인구이동 조건을 만족한다면
{
visited[ny][nx] = seq;
q.push({ ny,nx });
val += map[ny][nx]; // 전체값 갱신
cnt++; // 개수 갱신
movecnt = 1; // 인구이동이 발생했음을 기록
}
}
}
if (cnt == 1) // 인구 이동이 없었다면 그냥 넘김
{
seq++;
continue;
}
val /= cnt;
for (int y = 1; y <= n; y++)
{
for (int x = 1; x <= n; x++)
{
if (visited[y][x] == seq)
map[y][x] = val; // 인구 갱신
}
}
seq++;
}
}
if (!movecnt)
break;
ans++; // movecnt가 0이 아니라면 인구이동이 있었다는 뜻이므로 ans 1 증가
resetvisited(); // 방문 기록 초기화
}
cout << ans;
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
input();
solution();
return 0;
}
Reference
この問題について(白駿16234号人口移転(C++)), 我々は、より多くの情報をここで見つけました https://velog.io/@ngchaneok/백준-16234번-인구-이동-Cテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol