โปรแกรม C++ เพื่อค้นหาจำนวนการเปลี่ยนแปลงที่จำเป็นในการรับจากปลายด้านหนึ่งไปยังอีกด้านหนึ่งในกริด

สมมติว่าเราได้รับตารางขนาด x * y ที่มีเซลล์สองประเภท บล็อกและยกเลิกการบล็อก เซลล์ที่ถูกบล็อกหมายความว่าไม่สามารถเข้าถึงเซลล์ได้ และยกเลิกการปิดกั้นหมายความว่าเซลล์นั้นสามารถเข้าถึงได้ เราเป็นตัวแทนของกริดในอาร์เรย์ 2 มิติ โดยให้เซลล์ที่ถูกบล็อกกำหนดเป็น '#' และกำหนดเซลล์ที่ไม่ถูกบล็อกเป็น '.' ตอนนี้ เราต้องเข้าถึงจากเซลล์ (0, 0) ถึงเซลล์ (x, y) เราสามารถทำได้เพียงสองครั้งเท่านั้น เราสามารถไปทางขวาของเซลล์หรือลงจากเซลล์ เราต้องจำไว้ว่า เราเข้าไปได้เฉพาะในเซลล์ที่ไม่ถูกบล็อก และ (0, 0) และ (x, y) เป็นเซลล์ที่ไม่ถูกบล็อกทั้งคู่ หากเราไม่สามารถเข้าถึง (x, y) จาก (0, 0) เราสามารถทำให้เซลล์ที่ถูกบล็อกเป็นเซลล์ที่ไม่ถูกบล็อกได้ เราต้องหาจำนวนขั้นต่ำของการดำเนินการที่เปลี่ยนแปลงเพื่อดำเนินการไปถึงปลายทางของเราจากต้นทาง

ดังนั้น หากอินพุตเป็น x =4, y =4, grid ={"..#.", "#.#.", "#.##", "###."} ก็จะได้ผลลัพธ์ จะเป็น 1.

ต้องทำการเปลี่ยนแปลงเพียงครั้งเดียวเท่านั้น หากเราเปลี่ยนเซลล์ (2, 2) เป็นยกเลิกการปิดกั้นจากการถูกบล็อก เราก็สามารถเข้าถึง (3, 3) จาก (0, 0) ได้

ขั้นตอน

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

Define one 2D array mat
if grid[0, 0] is same as '#', then:
   mat[0, 0] := 1
Otherwise
   mat[0, 0] := 0
   for initialize i := 0, when i < x, update (increase i by 1), do:
      for initialize j := 0, when j < y, update (increase j by 1), do:
         if i + 1 < x, then:
            mat[i + 1, j] = minimum of (mat[i + 1, j], mat[i, j] + (1 if grid[i + 1, j] is same as '#' AND grid[i, j] is same as '.'))
   if j + 1 < y, then:
mat[i, j + 1] = minimum of (mat[i, j + 1], mat[i, j]+(1 if grid[i, j + 1] is same as '#' AND grid[i, j] is same as '.'))
return mat[x - 1, y - 1]

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;

int solve(int x, int y, vector<string> grid){
   vector<vector<int>> mat(x, vector<int>(y, 100));
   if(grid[0][0] == '#')
      mat[0][0] = 1;
   else
      mat[0][0] = 0;
   for(int i = 0; i < x; i++){
      for(int j = 0; j < y; j++){
         if(i + 1 < x){
            mat[i + 1][j] = min(mat[i + 1][j], mat[i][j] + (grid[i + 1][j] == '#' && grid[i][j] == '.'));
         }
         if(j + 1 < y){
            mat[i][j + 1] = min(mat[i][j + 1],mat[i][j]+(grid[i][j + 1] == '#' && grid[i][j] == '.'));
         }
      }
   }
   return mat[x - 1][y - 1];
}
int main() {
   int x = 4, y = 4;
   vector<string> grid = {"..#.", "#.#.", "#.##", "###."};
   cout<< solve(x, y, grid);
   return 0;
}

อินพุต

4, 4, {"..#.", "#.#.", "#.##", "###."}