[白俊][BFS][C+]7569号トマト

50916 ワード
白駿 BFS アルゴリズム#アルゴリズム# テキストリンク

質問する


7569-トマト


に答える


アルゴリズム#アルゴリズム#


  • トマト倉庫を3 D座標系と見なし、入力値M(横)、N(縦)、H(高さ)を3 D配列として宣言します.int box[MAX][MAX][MAX];

  • このとき,熟トマト(1)の座標と未熟トマト(0)の個数を同時に受け入れる.
    熟したトマトの座標はBFSを開始する点を知る必要がある.
    未熟トマトの個数は「トマトが完熟していない状況」を知るために必要です.
    次の入力を受け入れることができます.
    •     // Tomato => {h, y, x}
    vector<Tomato> targets;
    // 높이만큼 반복
    for (int i = 0; i < H; i++)
    {
        // 세로(행)만큼 반복
        for (int j = 0; j < N; j++)
        {
            // 가로(열)만큼 반복
            for (int k = 0; k < M; k++)
            {
                // box[높이][세로][가로]
                cin >> box[i][j][k];

                // 익어있는 토마토의 좌표
                if (box[i][j][k] == 1)
                    targets.push_back({i, j, k});
                // 익지 않은 토마토의 갯수
                else if (box[i][j][k] == 0)
                    zero++;
            }
        }
    }
    BFSを実行するために
  • 3 D座標系を使用する必要があるため、次の座標移動のためにdh[], dy[], dx[]配列を作成し、値を入れます.
    下図に示すように、h、y、xを軸とした3次元座標系が見られます.△座標軸の順序や名称は違いますが、x、y、z座標系と何の違いもありません.自分の好みで調整すればいいです.数学の授業のように、いいですね.
    • // 12시, 1시, 3시, 6시, 7시, 9시
int dh[] = {0, 1, 0, 0, -1, 0};
int dy[] = {1, 0, 0, -1, 0, 0};
int dx[] = {0, 0, 1, 0, 0, -1};
  • 基本作業が完了しました.通常のBFSを実行しましょう.
    3 D座標系なので怖いかもしれませんが、2 D座標系で実行されているBFSの一歩ごとに1行のコードが追加されたバージョンだと考えれば便利です.
    • int Solve(vector<Tomato> &targets)
{
    // 익을 수 있는 토마토가 모두 익는데 걸리는 일 수
    int day = 0;

    // Tomato => {h, y, x}
    queue<Tomato> q;
    // targets => 시작 시 익어있는 토마토들의 좌표
    // queue에 targets를 모두 넣어두고 한 번에 BFS를 수행한다.
    for (auto target : targets)
        q.push(target);

    // BFS
    while (!q.empty())
    {
        int h = q.front().h;
        int y = q.front().y;
        int x = q.front().x;
        q.pop();

        // 일 수 업데이트
        // 시작 시 day = 1 이다.
        // 익은 토마토의 좌표부터 탐색하기 때문에(익은 토마토 = 1)
        day = max(day, box[h][y][x]);

        // dh[], dy[], dx[] 배열 원소 갯수 = 6
        for (int i = 0; i < 6; i++)
        {
            int nextH = h + dh[i];
            int nextY = y + dy[i];
            int nextX = x + dx[i];

            if (nextH < 0 || nextY < 0 || nextX < 0 ||
                nextH >= H || nextY >= N || nextX >= M)
                continue;

            // 다음 좌표에 토마토가 없거나 || 이미 익은 토마토라면 => 건너뛴다.
            if (box[nextH][nextY][nextX] == -1 || box[nextH][nextY][nextX] >= 1)
                continue;

            // 다음 좌표 = 현재 날짜 + 1
            // BFS를 사용한 최단 경로 탐색 알고리즘과 같다.
            box[nextH][nextY][nextX] = box[h][y][x] + 1;
            q.push({nextH, nextY, nextX});
            // zero => 익지 않은 토마토의 갯수
            // 토마토가 익었으니 익지 않은 토마토의 갯수를 하나 줄여준다.
            zero--;
        }
    }

    // day에 -1 한 값을 return 해준다.
    // 문제에서 시작 시 일 수 = 0 인데 우리는 위에서 day = 1부터 BFS를 시작했으므로
    return day - 1;
}
  • 問題要求の出力値
    1)未熟トマトがある場合=>-1
    2)完熟時=>所要日数
    したがって、以下のように出力することができる.
    •     if (zero > 0)
        cout << "-1";
    else
        cout << day;

    コード#コード#

    #include <bits/stdc++.h>

using namespace std;

#define MAX 101

int M, N, H;
int box[MAX][MAX][MAX];
int zero = 0;

// 12시, 1시, 3시, 6시, 7시, 9시
int dh[] = {0, 1, 0, 0, -1, 0};
int dy[] = {1, 0, 0, -1, 0, 0};
int dx[] = {0, 0, 1, 0, 0, -1};

struct Tomato
{
    int h = 0;
    int y = 0;
    int x = 0;
};

int Solve(vector<Tomato> &targets)
{
    int day = 0;

    queue<Tomato> q;
    for (auto target : targets)
        q.push(target);

    while (!q.empty())
    {
        int h = q.front().h;
        int y = q.front().y;
        int x = q.front().x;
        q.pop();

        day = max(day, box[h][y][x]);

        for (int i = 0; i < 6; i++)
        {
            int nextH = h + dh[i];
            int nextY = y + dy[i];
            int nextX = x + dx[i];

            if (nextH < 0 || nextY < 0 || nextX < 0 ||
                nextH >= H || nextY >= N || nextX >= M)
                continue;

            if (box[nextH][nextY][nextX] == -1 || box[nextH][nextY][nextX] >= 1)
                continue;

            box[nextH][nextY][nextX] = box[h][y][x] + 1;
            q.push({nextH, nextY, nextX});
            zero--;
        }
    }

    return day - 1;
}

int main()
{
    // 가로 >> 세로 >> 높이
    cin >> M >> N >> H;

    vector<Tomato> targets;

    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)
                    targets.push_back({i, j, k});
                else if (box[i][j][k] == 0)
                    zero++;
            }

    int day = Solve(targets);

    if (zero > 0)
        cout << "-1";
    else
        cout << day;
}

    コメントコード

    #include <bits/stdc++.h>

using namespace std;

#define MAX 101

int M, N, H;
int box[MAX][MAX][MAX];
int zero = 0;

// 12시, 1시, 3시, 6시, 7시, 9시
int dh[] = {0, 1, 0, 0, -1, 0};
int dy[] = {1, 0, 0, -1, 0, 0};
int dx[] = {0, 0, 1, 0, 0, -1};

struct Tomato
{
    int h = 0;
    int y = 0;
    int x = 0;
};

int Solve(vector<Tomato> &targets)
{
    // 익을 수 있는 토마토가 모두 익는데 걸리는 일 수
    int day = 0;

    // Tomato => {h, y, x}
    queue<Tomato> q;
    // targets => 시작 시 익어있는 토마토들의 좌표
    // queue에 targets를 모두 넣어두고 한 번에 BFS를 수행한다.
    for (auto target : targets)
        q.push(target);

    // BFS
    while (!q.empty())
    {
        int h = q.front().h;
        int y = q.front().y;
        int x = q.front().x;
        q.pop();

        // 일 수 업데이트
        // 시작 시 day = 1 이다.
        // 익은 토마토의 좌표부터 탐색하기 때문에(익은 토마토 = 1)
        day = max(day, box[h][y][x]);

        // dh[], dy[], dx[] 배열 원소 갯수 = 6
        for (int i = 0; i < 6; i++)
        {
            int nextH = h + dh[i];
            int nextY = y + dy[i];
            int nextX = x + dx[i];

            if (nextH < 0 || nextY < 0 || nextX < 0 ||
                nextH >= H || nextY >= N || nextX >= M)
                continue;

            // 다음 좌표에 토마토가 없거나 || 이미 익은 토마토라면 => 건너뛴다.
            if (box[nextH][nextY][nextX] == -1 || box[nextH][nextY][nextX] >= 1)
                continue;

            // 다음 좌표 = 현재 날짜 + 1
            // BFS를 사용한 최단 경로 탐색 알고리즘과 같다.
            box[nextH][nextY][nextX] = box[h][y][x] + 1;
            q.push({nextH, nextY, nextX});
            // zero => 익지 않은 토마토의 갯수
            // 토마토가 익었으니 익지 않은 토마토의 갯수를 하나 줄여준다.
            zero--;
        }
    }

    // day에 -1 한 값을 return 해준다.
    // 문제에서 시작 시 일 수 = 0 인데 우리는 위에서 day = 1부터 BFS를 시작했으므로
    return day - 1;
}

int main()
{
    // 가로 >> 세로 >> 높이
    cin >> M >> N >> H;

    // Tomato => {h, y, x}
    vector<Tomato> targets;
    // 높이만큼 반복
    for (int i = 0; i < H; i++)
    {
        // 세로(행)만큼 반복
        for (int j = 0; j < N; j++)
        {
            // 가로(열)만큼 반복
            for (int k = 0; k < M; k++)
            {
                // box[높이][세로][가로]
                cin >> box[i][j][k];

                // 익어있는 토마토의 좌표
                if (box[i][j][k] == 1)
                    targets.push_back({i, j, k});
                // 익지 않은 토마토의 갯수
                else if (box[i][j][k] == 0)
                    zero++;
            }
        }
    }

    int day = Solve(targets);

    if (zero > 0)
        cout << "-1";
    else
        cout << day;
}

    似たような問題


    4963-島の数

    barrierとsmp_mb
    yumディスクソースに切断