ส้มเน่าใน C++

สมมติว่าเรามีกริด แต่ละเซลล์สามารถมีค่าได้ 3 ค่า:

• ค่า 0 สำหรับเซลล์ว่าง

• ค่า 1 สำหรับส้มสด

• ค่า 2 สำหรับส้มเน่า

ทุกนาที ส้มสดที่อยู่ติดกับส้มเน่าจะกลายเป็นส้มเน่า

เราต้องหาจำนวนนาทีขั้นต่ำที่ต้องรอจนกว่าไม่จะมีเซลล์ไหนเป็นส้มสด ถ้าเป็นไปไม่ได้ ให้คืนค่า -1

เช่น ถ้าอินพุตเป็น [[2,1,1],[1,1,0],[0,1,1]] ผลลัพธ์จะเป็น 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

• minutes := 0

• rowMax := จำนวนแถวของ grid

• colMax := จำนวนคอลัมน์ของ grid

• freshLeft := false

• newGrid := grid

• ทำซ้ำ while true:

  • newGrid := grid

  • flag := false

  • freshLeft := false

  • ลูป i จาก 0 ถึง rowMax-1:

    • ลูป j จาก 0 ถึง colMax-1:

      • ถ้า newGrid[i][j] เป็น 1 ให้:

        • ถ้า (i-1 >= 0 และ newGrid[i-1][j] เป็น 2) หรือ (i+1 < rowMax และ newGrid[i+1][j] เป็น 2) หรือ (j-1 >= 0 และ newGrid[i][j-1] เป็น 2) หรือ (j+1 < colMax และ newGrid[i][j+1] เป็น 2) ให้:

          • grid[i][j] := 2

          • flag := true

        • freshLeft := true

  • ถ้า flag เป็นจริง ให้:

    • เพิ่ม minutes ขึ้น 1

  • มิฉะนั้น ให้ออกจากลูป

• คืนค่า (ถ้า freshLeft ไม่เป็นจริง ให้ minutes มิฉะนั้น -1)

ตัวอย่าง (C++)

ลองดูการนำไปใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#include <bits/stdc++.h> using namespace std; class Solution { public:    int orangesRotting(vector<vector<int>> &grid) {       int minutes = 0;       int rowMax = grid.size();       int colMax = grid[0].size();       bool freshLeft = false;       auto newGrid = grid;       while (true) {          newGrid = grid;          bool flag = false;          freshLeft = false;          for (int i = 0; i < rowMax; i++) {             for (int j = 0; j < colMax; j++) {                if (newGrid[i][j] == 1) {                   if ((i - 1 >= 0 && newGrid[i - 1][j] == 2) or (i + 1 < rowMax && newGrid[i + 1][j] == 2) or (j - 1 >= 0 && newGrid[i][j - 1] == 2) or (j + 1 < colMax && newGrid[i][j + 1] == 2)) {                      grid[i][j] = 2;                      flag = true;                   }                   freshLeft = true;                }             }          }          if (flag)             minutes++;          else             break;       }       return (freshLeft != true) ? minutes : -1;    } }; main() {    Solution ob;    vector<vector<int>> v = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};    cout << (ob.orangesRotting(v)); }

อินพุต

{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}

เอาต์พุต

4