アレイ内の移動
Problem link: https://www.acmicpc.net/problem/1981
一見DP問題であるが、実際は1939号の重量制限と非常に似た二分探索問題である.
「最大値の最小値の差が最小の場合」はわかりにくいですが、「最大値の最小値の差はXですか?」簡単です.
Xを探す過程は上限を探せばいい
Xが固定されている場合、配列の各数の範囲が200未満であるため、差Xのmin/maxの組み合わせは十分に展開することができる.
一見DP問題であるが、実際は1939号の重量制限と非常に似た二分探索問題である.
「最大値の最小値の差が最小の場合」はわかりにくいですが、「最大値の最小値の差はXですか?」簡単です.
Xを探す過程は上限を探せばいい
Xが固定されている場合、配列の各数の範囲が200未満であるため、差Xのmin/maxの組み合わせは十分に展開することができる.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int kMaxN = 100;
const int kMaxElem = 200;
int N;
int ARR[kMaxN][kMaxN];
bool Bfs(const int min, const int max)
{
if (min > ARR[0][0] || ARR[0][0] > max || min > ARR[N - 1][N - 1] || ARR[N - 1][N - 1] > max)
{
return false;
}
vector<bool> visited(N * N, false);
queue<int> q;
const int dr[4] = { -1, 0, 1, 0 };
const int dc[4] = { 0, 1, 0, -1 };
visited[0] = true;
q.push(0);
while (!q.empty())
{
int r = q.front() / N;
int c = q.front() % N;
q.pop();
if (r + 1 == N && c + 1 == N)
{
return true;
}
for (int d = 0; d < 4; ++d)
{
int nr = r + dr[d];
int nc = c + dc[d];
int nidx = nr * N + nc;
if (0 > nr || nr >= N || 0 > nc || nc >= N)
{
continue;
}
if (min <= ARR[nr][nc] && ARR[nr][nc] <= max && !visited[nidx])
{
visited[nidx] = true;
q.push(nidx);
}
}
}
return false;
}
int Solve(void)
{
int left = 0;
int right = kMaxElem;
while (left < right)
{
int mid = (left + right) / 2;
bool possible = false;
for (int min = 0; min + mid <= kMaxElem; ++min)
{
if (Bfs(min, min + mid))
{
possible = true;
break;
}
}
if (possible)
{
right = mid;
}
else
{
left = mid + 1;
}
}
return left;
}
int main(void)
{
// For Faster IO
ios_base::sync_with_stdio(false);
cout.tie(nullptr);
cin.tie(nullptr);
// Read Input
cin >> N;
for (int r = 0; r < N; ++r)
{
for (int c = 0; c < N; ++c)
{
cin >> ARR[r][c];
}
}
// Solve
cout << Solve() << '\n';
return 0;
}
Reference
この問題について(アレイ内の移動), 我々は、より多くの情報をここで見つけました https://velog.io/@aram_father/배열에서-이동テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol