BOJ 7569トマト
質問する
注意事項
できるだけ深いものを選びます.(過去日数)
アップルが全て熟成している場合は、BFSナビを終了する時です.
(Q中には熟していないりんごしか入っていません)
質問に最小日数を求めさせます.
BFSを使用すると、アクセス先がアクセスされなくなり、パスが最小化されます.
そのため、最小値を得るために除去する必要はない.
私は考えが浅くて、最小を求めたいです.おかげさまで長い間挿し込みました^^
私はあなたに最高価格を探してもらいます.あなたが最高価格を探しているからといって反感を持ってはいけません.
DPだけを解いて、必死に最高値を探しています.(minで解決しようとする)
コード#コード#
// 2021.10.01 14:03:46
// 7569 https://boj.kr/7569
#include <bits/stdc++.h>
using namespace std;
const int dz[6] = {1, -1, 0, 0, 0, 0};
const int dy[6] = {0, 0, 1, -1, 0, 0};
const int dx[6] = {0, 0, 0, 0, 1, -1};
int box[101][101][101];
int n, m, h;
class Node
{
public:
int z, y, x, day;
void ripe()
{
box[z][y][x] = 1;
}
bool isValid()
{
return this->z >= 0 && this->z < h && this->y >= 0 && this->y < n && this->x >= 0 && this->x < m;
}
};
int bfs(vector<Node> &startNodes)
{
queue<Node> q;
for (auto &node : startNodes)
{
q.push(node);
}
int day = 0;
while (!q.empty())
{
Node cur = q.front();
q.pop();
day = max(day, cur.day);
for (int next = 0; next < 6; next++)
{
Node nextNode = Node({cur.z + dz[next], cur.y + dy[next], cur.x + dx[next], cur.day + 1});
if (nextNode.isValid() && box[nextNode.z][nextNode.y][nextNode.x] == 0)
{
q.push(nextNode);
nextNode.ripe();
}
}
}
return day;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> m >> n >> h;
vector<Node> startNodes;
for (int i = 0; i < h; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < m; k++)
{
cin >> box[i][j][k];
if (box[i][j][k] == 1)
{
startNodes.push_back(Node({i, j, k, 0}));
}
}
}
}
int answer = bfs(startNodes);
for (int i = 0; i < h; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < m; k++)
if (box[i][j][k] == 0)
{
cout << -1;
return 0;
}
cout << answer;
}
結果
Reference
この問題について(BOJ 7569トマト), 我々は、より多くの情報をここで見つけました https://velog.io/@0chil/BOJ-7569-토마토テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol