[C++]白駿7576:トマト
#include <iostream>
#include <utility> //pair
#include <queue>
using namespace std;
int map[101][101][101]; // 1 : 익은 토마토, 0 : 익지 않은 토마토, -1 : 토마토 없음
queue<pair<pair<int, int>, int> > q; // h, y, x
// 상하좌우위아래 탐색
int dx[6] = {1, -1, 0, 0, 0, 0};
int dy[6] = {0, 0, 1, -1, 0, 0};
int dh[6] = {0, 0, 0, 0, 1, -1};
bool allTomato = true; // 모든 토마토 익어있는 경우
int M, N, H; // 가로, 세로, 높이
int cnt = 0; // 토마토 모두 익을 때 까지 걸리는 시간
void BFS(){
while(!q.empty()){
int x = q.front().second;
int y = q.front().first.second;
int h = q.front().first.first; // 노드의 좌표 구하기
q.pop();
for(int i = 0; i < 6; i++){
int nx = x + dx[i];
int ny = y + dy[i];
int nh = h + dh[i];
if(nx < 1 || ny < 1 || nh < 1 || nx > M || ny > N || nh > H){
continue;
}
if(map[nh][ny][nx] == 0){ // 안익은 토마토가 있을 때
map[nh][ny][nx] = map[h][y][x] + 1; // 날짜 더하기
q.push({{nh, ny}, nx});
}
}
}
}
int main(int argc, char* argv[]){
scanf("%d %d %d", &M, &N, &H);
for(int i=1; i<=H; i++){
for(int j=1; j<=N; j++){
for(int k=1; k<=M; k++){
scanf("%d", &map[i][j][k]); // 입력받기
if(map[i][j][k] == 1){ // 익은 토마토일 때
q.push({{i, j}, k});
} else if(map[i][j][k] == 0){
allTomato = false;
}
}
}
}
if(allTomato){ // 처음부터 모든 토마토 익어있는 경우
printf("0");
return 0;
}
BFS();
// for(int i=1; i<=H; i++){
// for(int j=1; j<=N; j++){
// for(int k=1; k<=M; k++){
// printf("%d ", map[i][j][k]);
// }
// printf("\n");
// }
// }
for(int i=1; i<=H; i++){
for(int j=1; j<=N; j++){
for(int k=1; k<=M; k++){
if(map[i][j][k] == 0){ // 모두 익지 않았을 때
printf("-1");
return 0;
}
if(cnt < map[i][j][k]){ // 최대 일 수 구하기
cnt = map[i][j][k];
}
}
}
}
printf("%d", cnt-1); // 토마토 익은 것 1부터 시작
return 0;
}
トマトのアップグレードバージョンの問題上下左右を確認するために、上へ、下へ、左へ、右へ...そのため、6種類の場合、数を確認するだけで済みます.気をつけて最初は、すべての状況の数を配列に入れたいと思っていましたが、これは非常に必要ではありません.
cntを数えるために、直接地図で表し、アクセスするかどうかを表す必要はありません.ということで、7576号とは違って、今回は思い切って訪問をキャンセルしました.
pairに値を入力する場合はmake pairを使用するのが望ましいが、{}を使用すると直感的で容易である.
Reference
この問題について([C++]白駿7576:トマト), 我々は、より多くの情報をここで見つけました https://velog.io/@lamknh/C-백준-7576-토마토-7en3569nテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol