グリッド内のブロックされていないセルから別のブロックされていないセルに到達するための移動の最大数を見つけるためのC++プログラム

ブロックされたセルとブロックされていないセルの2種類のセルを含む次元h*wのグリッドが与えられたとします。ブロックされたセルはセルにアクセスできないことを意味し、ブロックされていないことはセルにアクセスできることを意味します。ブロックされたセルは「＃」で示され、ブロックされていないセルは「。」で示される2D配列でグリッドを表します。ここで、ブロックされていないセルからグリッド内の別のブロックされていないセルに到達する必要があります。実行できる移動は2つだけで、垂直に移動することも、水平に移動することもできます。斜めに移動することはできません。ブロックされていないセルにしか移動できないことを覚えておく必要があります。したがって、グリッド内の別のブロックされていないセルからブロックされていないセルに到達するために必要な移動の最大数を見つける必要があります。

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

セル（0,0）から、セル（2、0）に到達するには、最大4回の移動が必要です。

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

Define an array xdir of size: 4 := {1, 0, - 1, 0}
Define an array ydir of size: 4 := {0, 1, 0, - 1}
Define one 2D array dist
Define one 2D array reset
res := 0
for initialize i := 0, when i < h, update (increase i by 1), do:
   for initialize j := 0, when j < w, update (increase j by 1), do:
      dist := reset
      if grid[i, j] is same as '.', then:
         dist[i, j] := 0
         Define one queue q containing integer pairs
         insert make_pair(i, j) into q
         while (not q is empty), do:
            x := first element of the leftmost element in the q
            y := second element of the leftmost element in the q
            res := maximum of (dist[x, y] and res)
            delete leftmost element from q
            for initialize k := 0, when k < 4, update (increase k by 1), do:
               px := x + xdir[k]
               py := y + ydir[k]
               if px >= 0 and px < h and py >= 0 and py < w, then:
                  if grid[px, py] is same as '.', then:
                     if dist[px, py] is same as -1, then:
                        dist[px, py] := dist[x, y] + 1
                        insert pair(px, py) into q
return res

例

理解を深めるために、次の実装を見てみましょう-

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

int solve(int h, int w, vector<string> grid){
   int xdir[4] = {1, 0, -1, 0};
   int ydir[4] = {0, 1, 0, -1};
   vector<vector<int>> dist(h, vector<int>(w, -1));
   vector<vector<int>> reset(h, vector<int>(w, -1));
   int res = 0;
   for(int i = 0; i < h; i++){
      for(int j = 0; j < w; j++){
          dist = reset;
          if(grid[i][j] == '.'){
             dist[i][j] = 0;
             queue<pair<int,int>> q;
             q.push(make_pair(i, j));
             while(!q.empty()){
                int x = q.front().first;
                int y = q.front().second;
                res = max(dist[x][y], res);
                q.pop();
                for(int k = 0; k < 4; k++){
                   int px = x + xdir[k];
                   int py = y + ydir[k];
                   if(px >= 0 && px < h && py >= 0 && py < w){
                      if(grid[px][py] == '.'){
                         if(dist[px][py] == -1){
                            dist[px][py] = dist[x][y] + 1; q.push(make_pair(px, py));
                         }
                      }
                   }
                }
             }
         }
      }
   }
   return res;
}
int main() {
   int h = 4, w = 4;
   vector<string> grid = {"..#.", "#.#.", "..##", "###."};
   cout << solve(h, w, grid);
   return 0;
}

入力

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

出力

4