C++ 그리드에서 차단되지 않은 셀에 다른 차단되지 않은 셀에 도달하기 위한 최대 이동 횟수를 찾는 프로그램

<시간/>

차단된 것과 차단되지 않은 두 가지 유형의 셀을 포함하는 h * w 차원의 그리드가 제공된다고 가정합니다. 차단된 셀은 셀에 액세스할 수 없음을 의미하고 차단 해제는 셀에 액세스할 수 있음을 의미합니다. 차단된 셀은 '#'으로 표시되고 차단되지 않은 셀은 '.'로 표시되는 2D 배열로 그리드를 나타냅니다. 이제 우리는 차단되지 않은 셀에서 그리드의 차단되지 않은 다른 셀로 도달해야 합니다. 우리는 두 가지 움직임만 수행할 수 있습니다. 수직으로 이동하거나 수평으로 이동할 수 있습니다. 우리는 대각선으로 이동할 수 없습니다. 우리는 차단되지 않은 세포로만 이동할 수 있음을 명심해야 합니다. 따라서 그리드의 다른 차단되지 않은 셀에서 차단되지 않은 셀에 도달하는 데 필요한 최대 이동 횟수를 찾아야 합니다.

따라서 입력이 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, {"..#.", "#.#.", "..##", "###."}