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

สมมติว่าเรามีตาราง ซึ่งในแต่ละเซลล์สามารถมีค่าหนึ่งในสามค่านี้ -

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

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

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

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

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

ดังนั้น หากอินพุตเป็น [[2,1,1],[1,1,0],[0,1,1]] ผลลัพธ์จะเป็น 4

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

• นาที :=0

• rowMax :=ขนาดแถวของตาราง

• colMax :=ขนาด col ของกริด

• freshLeft :=เท็จ

• newGrid :=กริด

• ในขณะที่ true ไม่ใช่ศูนย์ ให้ทำ -

  • newGrid :=กริด

  • ธง :=เท็จ

  • freshLeft :=เท็จ

  • สำหรับการเริ่มต้น i :=0 เมื่อ i

    • สำหรับการเริ่มต้น j :=0 เมื่อ j

      • ถ้า newGrid[i, j] เหมือนกับ 1 แล้ว −

        • ถ้า (i-1>=0 และ newGrid[i-1,j] คือ 2) หรือ (i+1 =0 และ newGrid[ i,j-1] คือ 2) หรือ (j+1>=0 และ newGrid[i,j+1] คือ 2) จากนั้น

          • กริด[i, j] :=2

          • ธง :=จริง

        • freshLeft :=จริง

  • ถ้าแฟล็กไม่ใช่ศูนย์ ดังนั้น −

    • (เพิ่มนาที 1)

  • มิฉะนั้น

    • ออกจากวง

• return (ถ้า freshLeft ไม่เท่ากับ true จะเป็นนาที มิฉะนั้น -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