グリッド内の一方の端からもう一方の端に到達するために必要な変更の数を見つけるためのC++プログラム

ブロックされたセルとブロックされていないセルの2種類のセルを含む次元x*yのグリッドが与えられたとします。ブロックされたセルはセルにアクセスできないことを意味し、ブロックされていないことはセルにアクセスできることを意味します。ブロックされたセルは「＃」で示され、ブロックされていないセルは「。」で示される2D配列でグリッドを表します。ここで、セル（0、0）からセル（x、y）に到達する必要があります。実行できる移動は2つだけで、セルの右に移動するか、セルから下に移動することができます。ブロックされていないセルにしか入ることができず、（0、0）と（x、y）は両方ともブロックされていないセルであることに注意する必要があります。 （0、0）から（x、y）に到達できない場合は、ブロックされたセルをブロックされていないセルにすることができます。ソースから目的地に到達するために実行する変更操作の最小数を見つける必要があります。

したがって、入力がx =4、y =4、grid ={"..＃。"、 "＃。＃。"、 "＃。##"、 "###。"}の場合、出力は1になります。

変更操作は1回だけ実行する必要があります。セル（2、2）をブロック解除からブロック解除に変更すると、（0、0）から（3、3）に到達できます。

ステップ

これを解決するには、次の手順に従います-

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, {"..#.", "#.#.", "#.##", "###."}

出力

1