Chương trình C ++ để tìm ra số lượng thay đổi cần thiết để thực hiện từ đầu này sang đầu kia trong lưới

Giả sử, chúng ta được cung cấp một lưới có kích thước x * y chứa hai loại ô, bị chặn và không bị chặn. Các ô bị chặn có nghĩa là các ô không thể truy cập được và việc bỏ chặn có nghĩa là các ô đó có thể truy cập được. Chúng tôi biểu diễn lưới trong một mảng 2D trong đó các ô bị chặn được cho là '#' và các ô không bị chặn được cho là '.'. Bây giờ, chúng ta phải tiếp cận từ ô (0, 0) đến ô (x, y). Chúng ta chỉ có thể thực hiện hai lần di chuyển, chúng ta có thể đi bên phải của một ô hoặc đi xuống từ một ô. Chúng ta phải lưu ý rằng, chúng ta chỉ có thể đi trong các ô không bị chặn và (0, 0) và (x, y) đều là các ô không bị chặn. Nếu chúng ta không thể tiếp cận (x, y) từ (0, 0), chúng ta có thể biến một ô bị chặn thành ô không bị chặn. Chúng tôi phải tìm số lượng tối thiểu các hoạt động thay đổi cần thực hiện để đến đích từ nguồn.

Vì vậy, nếu đầu vào là x =4, y =4, grid ={".. #.", "#. #.", "#. ##", "###."}, Thì đầu ra sẽ là 1.

Chỉ một thao tác thay đổi phải được thực hiện. Nếu chúng ta thay đổi ô (2, 2) thành bỏ chặn khỏi bị chặn, thì chúng ta có thể đến (3, 3) từ (0, 0).

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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;
}

Đầu vào

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

Đầu ra

1